fork download
copy 
  1. #pragma GCC optimize("Ofast")
  2. #pragma GCC optimize("unroll-loops")
  3. #pragma GCC optimize("inline")
  4. #include<bits/stdc++.h>
  5. using namespace std;
  6. template<class T> struct cLtraits_identity{
  7.   using type = T;
  8. }
  9. ;
  10. template<class T> using cLtraits_try_make_signed =
  11.   typename conditional<
  12.     is_integral<T>::value,
  13.     make_signed<T>,
  14.     cLtraits_identity<T>
  15.     >::type;
  16. template <class S, class T> struct cLtraits_common_type{
  17.   using tS = typename cLtraits_try_make_signed<S>::type;
  18.   using tT = typename cLtraits_try_make_signed<T>::type;
  19.   using type = typename common_type<tS,tT>::type;
  20. }
  21. ;
  22. template<class S, class T> inline auto max_L(S a, T b)
  23. -> typename cLtraits_common_type<S,T>::type{
  24.   return (typename cLtraits_common_type<S,T>::type) a >= (typename cLtraits_common_type<S,T>::type) b ? a : b;
  25. }
  26. #define ISPRIME_PRE_CALC_SIZE 1000000
  27. char isPrime_prime_table[ISPRIME_PRE_CALC_SIZE];
  28. template<class T> inline int isPrime(T n);
  29. void isPrime32_init(void);
  30. int isPrime32_sub(int b, unsigned n);
  31. int isPrime32(unsigned n);
  32. int isPrime64_sub(long long b, unsigned long long n);
  33. int isPrime64(unsigned long long n);
  34. inline int my_getchar_unlocked(){
  35.   static char buf[1048576];
  36.   static int s = 1048576;
  37.   static int e = 1048576;
  38.   if(s == e && e == 1048576){
  39.     e = fread_unlocked(buf, 1, 1048576, stdin);
  40.     s = 0;
  41.   }
  42.   if(s == e){
  43.     return EOF;
  44.   }
  45.   return buf[s++];
  46. }
  47. inline void rd(int &x){
  48.   int k;
  49.   int m=0;
  50.   x=0;
  51.   for(;;){
  52.     k = my_getchar_unlocked();
  53.     if(k=='-'){
  54.       m=1;
  55.       break;
  56.     }
  57.     if('0'<=k&&k<='9'){
  58.       x=k-'0';
  59.       break;
  60.     }
  61.   }
  62.   for(;;){
  63.     k = my_getchar_unlocked();
  64.     if(k<'0'||k>'9'){
  65.       break;
  66.     }
  67.     x=x*10+k-'0';
  68.   }
  69.   if(m){
  70.     x=-x;
  71.   }
  72. }
  73. inline int rd_int(void){
  74.   int x;
  75.   rd(x);
  76.   return x;
  77. }
  78. struct MY_WRITER{
  79.   char buf[1048576];
  80.   int s;
  81.   int e;
  82.   MY_WRITER(){
  83.     s = 0;
  84.     e = 1048576;
  85.   }
  86.   ~MY_WRITER(){
  87.     if(s){
  88.       fwrite_unlocked(buf, 1, s, stdout);
  89.     }
  90.   }
  91. }
  92. ;
  93. MY_WRITER MY_WRITER_VAR;
  94. void my_putchar_unlocked(int a){
  95.   if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){
  96.     fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);
  97.     MY_WRITER_VAR.s = 0;
  98.   }
  99.   MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;
  100. }
  101. inline void wt_L(char a){
  102.   my_putchar_unlocked(a);
  103. }
  104. inline void wt_L(int x){
  105.   int s=0;
  106.   int m=0;
  107.   char f[10];
  108.   if(x<0){
  109.     m=1;
  110.     x=-x;
  111.   }
  112.   while(x){
  113.     f[s++]=x%10;
  114.     x/=10;
  115.   }
  116.   if(!s){
  117.     f[s++]=0;
  118.   }
  119.   if(m){
  120.     my_putchar_unlocked('-');
  121.   }
  122.   while(s--){
  123.     my_putchar_unlocked(f[s]+'0');
  124.   }
  125. }
  126. template<class T> inline T pow2_L(T a){
  127.   return a*a;
  128. }
  129. inline long long Isqrt_f_L(const long long n){
  130.   long long r = sqrt(n);
  131.   r =max_L(r-2, 0);
  132.   while((pow2_L((r+1)))<= n ){
  133.     r++;
  134.   }
  135.   return r;
  136. }
  137. int main(){
  138.   int Lj4PdHRW;
  139.   {
  140.     isPrime32_init();
  141.   }
  142.   int KL2GvlyY = rd_int();
  143.   for(Lj4PdHRW=(0);Lj4PdHRW<(KL2GvlyY);Lj4PdHRW++){
  144.     int X;
  145.     rd(X);
  146.     if(X==0){
  147.       wt_L(3);
  148.       wt_L('\n');
  149.       continue;
  150.     }
  151.     if(isPrime(X)){
  152.       wt_L(1);
  153.       wt_L('\n');
  154.       continue;
  155.     }
  156.     if(isPrime(X+X+1) || isPrime(X+X-1)){
  157.       wt_L(2);
  158.       wt_L('\n');
  159.       continue;
  160.     }
  161.     if(X >= 0){
  162.       X =X;
  163.     }
  164.     else{
  165.       X =-X+1;
  166.     }
  167.     for(;;){
  168.       if(isPrime(X)){
  169.         wt_L(2*X);
  170.         wt_L('\n');
  171.         break;
  172.       }
  173.       if(isPrime(X+X+1)){
  174.         wt_L(2*X+1);
  175.         wt_L('\n');
  176.         break;
  177.       }
  178.       X++;
  179.     }
  180.   }
  181.   return 0;
  182. }
  183. template<class T> inline int isPrime(T n){
  184.   T i;
  185.   if(n<=1){
  186.     return 0;
  187.   }
  188.   if(n <= (1ULL<<32) - 1){
  189.     return isPrime32(n);
  190.   }
  191.   if(n <= (1ULL<<63) - 1 + (1ULL<<63)){
  192.     return isPrime64(n);
  193.   }
  194.   if(n<=3){
  195.     return 1;
  196.   }
  197.   if(n%2==0){
  198.     return 0;
  199.   }
  200.   for(i=3;i*i<=n;i+=2){
  201.     if(n%i==0){
  202.       return 0;
  203.     }
  204.   }
  205.   return 1;
  206. }
  207. int isPrime32_sub(int b, unsigned n){
  208.   unsigned i;
  209.   unsigned t = 0;
  210.   unsigned u = n-1;
  211.   unsigned long long nw;
  212.   unsigned long long nx;
  213.   while(!(u&1)){
  214.     t++;
  215.     u >>= 1;
  216.   }
  217.   nw = 1;
  218.   nx = b % n;
  219.   while(u){
  220.     if(u&1){
  221.       nw = (nw * nx) % n;
  222.     }
  223.     nx = (nx * nx) % n;
  224.     u >>= 1;
  225.   }
  226.   for(i=(0);i<(t);i++){
  227.     nx = (nw * nw) % n;
  228.     if(nx == 1 && nw != 1 && nw != n-1){
  229.       return 0;
  230.     }
  231.     nw = nx;
  232.   }
  233.   if(nw == 1){
  234.     return 1;
  235.   }
  236.   return 0;
  237. }
  238. int isPrime32(unsigned n){
  239.   if(n < 100000){
  240.     return isPrime_prime_table[n];
  241.   }
  242.   if(n % 2 == 0){
  243.     return 0;
  244.   }
  245.   if(!isPrime32_sub(2,n)){
  246.     return 0;
  247.   }
  248.   if(n<=1000000){
  249.     if(!isPrime32_sub(3,n)){
  250.       return 0;
  251.     }
  252.   }
  253.   else{
  254.     if(!isPrime32_sub(7,n)){
  255.       return 0;
  256.     }
  257.     if(!isPrime32_sub(61,n)){
  258.       return 0;
  259.     }
  260.   }
  261.   return 1;
  262. }
  263. int isPrime64_sub(long long b, unsigned long long n){
  264.   unsigned long long i;
  265.   unsigned long long t = 0;
  266.   unsigned long long u = n-1;
  267.   __uint128_t nw;
  268.   __uint128_t nx;
  269.   while(!(u&1)){
  270.     t++;
  271.     u >>= 1;
  272.   }
  273.   nw = 1;
  274.   nx = b % n;
  275.   while(u){
  276.     if(u&1){
  277.       nw = (nw * nx) % n;
  278.     }
  279.     nx = (nx * nx) % n;
  280.     u >>= 1;
  281.   }
  282.   for(i=(0);i<(t);i++){
  283.     nx = (nw * nw) % n;
  284.     if(nx == 1 && nw != 1 && nw != n-1){
  285.       return 0;
  286.     }
  287.     nw = nx;
  288.   }
  289.   if(nw == 1){
  290.     return 1;
  291.   }
  292.   return 0;
  293. }
  294. int isPrime64(unsigned long long n){
  295.   if(n < 100000){
  296.     return isPrime_prime_table[n];
  297.   }
  298.   if(n < (1ULL<<32)){
  299.     return isPrime32(n);
  300.   }
  301.   if(n % 2 == 0){
  302.     return 0;
  303.   }
  304.   if(!isPrime64_sub(2,n)){
  305.     return 0;
  306.   }
  307.   if(n <= 21652684502221ULL){
  308.     if(!isPrime64_sub(1215,n)){
  309.       return 0;
  310.     }
  311.     if(!isPrime64_sub(34862,n)){
  312.       return 0;
  313.     }
  314.     if(!isPrime64_sub(574237825,n)){
  315.       return 0;
  316.     }
  317.   }
  318.   else{
  319.     if(!isPrime64_sub(325,n)){
  320.       return 0;
  321.     }
  322.     if(!isPrime64_sub(9375,n)){
  323.       return 0;
  324.     }
  325.     if(!isPrime64_sub(28178,n)){
  326.       return 0;
  327.     }
  328.     if(!isPrime64_sub(450775,n)){
  329.       return 0;
  330.     }
  331.     if(!isPrime64_sub(9780504,n)){
  332.       return 0;
  333.     }
  334.     if(!isPrime64_sub(1795265022,n)){
  335.       return 0;
  336.     }
  337.   }
  338.   return 1;
  339. }
  340. void isPrime32_init(void){
  341.   int i;
  342.   int j;
  343.   int k;
  344.   k =Isqrt_f_L(ISPRIME_PRE_CALC_SIZE);
  345.   for(i=(2);i<(ISPRIME_PRE_CALC_SIZE);i++){
  346.     isPrime_prime_table[i] = 1;
  347.   }
  348.   for(i=(2);i<(k+1);i++){
  349.     if(isPrime_prime_table[i]){
  350.       for(j=(i*i);j<(ISPRIME_PRE_CALC_SIZE);j+=(i)){
  351.         isPrime_prime_table[j] = 0;
  352.       }
  353.     }
  354.   }
  355. }
  356. // cLay version 20210926-1
  357.  
  358. // --- original code ---
  359. // REP(rd_int()){
  360. //   int @X;
  361. //   if(X==0) wt(3), continue;
  362. //   if(isPrime(X)) wt(1), continue;
  363. //   if(isPrime(X+X+1) || isPrime(X+X-1)) wt(2), continue;
  364. //   X = if[X >= 0, X, -X+1];
  365. //   for(;;){
  366. //     if(isPrime(X)) wt(2*X), break;
  367. //     if(isPrime(X+X+1)) wt(2*X+1), break;
  368. //     X++;
  369. //   }
  370. // }
  371.  
Time limit exceeded #stdin #stdout 5s 5428KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/t3BnaV
language:
C++ (gcc 8.3)
created:
2 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!