fork(4) download
copy 
  1. #include<stdio.h>
  2. #define li long long int
  3. li BLOCK_SIZE;
  4.  
  5. li v[100005];
  6. li max_size;
  7. void sieve()
  8. {
  9.     li j=0;
  10.    li prime[100005]={0};
  11.     for(li i=2;i<100005;i++)
  12.     {
  13.       if(prime[i]==0)
  14.       {
  15.         max_size=j;
  16.         v[j]=i;
  17.         j++;
  18.         for(li j=2;j<100005;j++)
  19.         {
  20.         if(i*j<100005)
  21.         {
  22.           prime[i*j]=1;
  23.         }
  24.         }
  25.       }
  26.     }
  27.  
  28.  
  29. }
  30. int main()
  31. {
  32.   sieve();
  33.   li t;
  34.   scanf("%lld",&t);
  35.   while(t--)
  36.   {
  37.     li n;
  38.     scanf("%lld",&n);
  39.     li low=n-200;
  40.     if(low<2)
  41.     low=2;
  42.     li arr[202]={0};
  43.     //memset(arr,true,sizeof(arr));
  44.     for(li i=0;i<max_size;i++)
  45.     {
  46.       if(v[i]*v[i]>n)
  47.         break;
  48.       li d=(low/v[i])*v[i];
  49.       if(d<low)
  50.       {
  51.           d+=v[i];
  52.       }
  53.       if(d==v[i])
  54.       {
  55.           d+=v[i];
  56.       }
  57.      // cout<<"d"<<d<<endl;
  58.       for(li j=d;j<=n;j+=v[i])
  59.       {
  60.         arr[j-low]=1;
  61.       }
  62.     }
  63.     for(li i=n-1;i>=low;i--)
  64.     {
  65.       if(arr[i-low]==0)
  66.       {
  67.         printf("%lld\n",i);
  68.         break;
  69.       }
  70.     }
  71.  
  72.   }
  73. }
  74.  
Success #stdin #stdout 0.59s 16680KB
comments (?)
stdin
copy 
3
5 
10
17
stdout
copy 
3
7
13
https://ideone.com/qaRr12
language:
C++14 (gcc 8.3)
created:
7 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!