fork download
copy 
  1. #include<iostream>
  2. #include<bits/stdc++.h>
  3. #include<cstdio>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<stdio.h>
  7. #include<utility>
  8. #include<algorithm>
  9. #include<iomanip>
  10. #include<functional>
  11. #include<limits>
  12. #include<memory>
  13. #include<cstdlib>
  14. #include<cassert>
  15. #include<cctype>
  16. #include<cfloat>
  17. #include<stack>
  18. #include<queue>
  19. #include<deque>
  20. #include<iterator>
  21. #include<list>
  22. #include<vector>
  23. #include<map>
  24. #include<set>
  25. #include<string.h>
  26. #include<numeric>
  27. #include<ctime>
  28. #include<sstream>
  29.  
  30. using namespace std;
  31.  
  32. #define MOD 1000000007
  33. #define pb push_back
  34. #define pob pop_back
  35. #define pf push_front
  36. #define pof pop_front
  37. #define mp make_pair
  38. #define minr min_element
  39. #define maxr max_element
  40. #define mh make_heap
  41. #define ph push_heap
  42. #define poh pop_heap
  43. #define sd(n) scanf("%d",&n)
  44. #define sd2(i,j) scanf("%d%d",&i,&j)
  45. #define pd(n) printf("%d\n",n)
  46. #define sld(n) scanf("%lld",&n)
  47. #define sld2(i,j) scanf("%lld%lld",&i,&j)
  48. #define pld(n) printf("%lld\n",n)
  49. #define pld2(i,j) printf("%lld% lld\n",i,j);
  50. #define forb(i,n) for(int i=0;i<int(n);i++)
  51. #define fora(i,l,h) for(int i=int(l);i<=int(h);i++)
  52. #define ford(i,n) for(int i=int(n);i>=0;i--)
  53. #define all(a) a.begin(),a.end()
  54. #define set(a,x) memset(a,x,sizeof(a))
  55. #define li long long int
  56. li BLOCK_SIZE;
  57. inline bool mo_cmp(const pair<li,pair<li,li>> &x,
  58.         const pair<li,pair<li,li>> &y)
  59. {
  60.     int block_x = x.first / BLOCK_SIZE;
  61.     int block_y = y.first / BLOCK_SIZE;
  62.     if(block_x != block_y)
  63.         return block_x < block_y;
  64.     return x.second.first < y.second.first;
  65. }
  66. li n;
  67. li bit[100005]={0};
  68. void update(li a)
  69. {
  70.     for(li i=a;i<100005;i+=(i&-i))
  71.         bit[i]++;
  72.  
  73. }
  74. li qu(li a)
  75. {
  76.   li sum=0;
  77.   for(li i=a;i>0;i-=(i&-i))
  78.     sum+=bit[i];
  79.   return sum;
  80.  
  81. }
  82. li v[100005];
  83. li max_size;
  84. void sieve()
  85. {
  86.   //  li j=0;
  87.    li prime[100005]={0};
  88.     for(li i=2;i*i<100005;i++)
  89.     {
  90.       if(prime[i]==0)
  91.       {
  92.  
  93.         for(li j=2;j<100005;j++)
  94.         {
  95.         if(i*j<100005)
  96.         {
  97.           prime[i*j]=1;
  98.         }
  99.         }
  100.       }
  101.     }
  102.     li j=0;
  103.     for(li i=2;i<100005;i++)
  104.     {
  105.         if(prime[i]==0)
  106.         {
  107.         v[j]=i;
  108.         max_size=j;
  109.         j++;
  110.         }
  111.     }
  112.  
  113.  
  114. }
  115. int main()
  116. {
  117.   sieve();
  118.   li t;
  119.   scanf("%lld",&t);
  120.   while(t--)
  121.   {
  122.     li n;
  123.     scanf("%lld",&n);
  124.     li low=n-200;
  125.     if(low<2)
  126.     low=2;
  127.     li arr[202]={0};
  128.     for(li i=0;i<max_size;i++)
  129.     {
  130.       if(v[i]*v[i]>n)
  131.         break;
  132.       li d=(low/v[i])*v[i];
  133.       if(d<low)
  134.       {
  135.           d+=v[i];
  136.       }
  137.       if(d==v[i])
  138.       {
  139.           d+=v[i];
  140.       }
  141.       for(li j=d;j<=n;j+=v[i])
  142.       {
  143.         arr[j-low]=1;
  144.       }
  145.     }
  146.     for(li i=n-1;i>=low;i--)
  147.     {
  148.       if(arr[i-low]==0)
  149.       {
  150.         printf("%lld\n",i);
  151.         break;
  152.       }
  153.     }
  154.  
  155.   }
  156. }
  157.  
  158.  
  159.  
  160.  
  161.  
  162.  
Success #stdin #stdout 0s 17456KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
https://ideone.com/d1YZx8
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!