jakaria_hossain

Codeforce- Crazy jumper

Sep 24th, 2018
37
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define fastread()(ios_base::sync_with_stdio(false),cin.tie(NULL));
  4. typedef long long ll;
  5. #define N 12997800
  6. #define m 3606
  7. vector<int>prime;
  8. vector<bool>isprime(N,true);
  9. void primefactor()
  10. {
  11. int pos=1,i,j;
  12. for(i=4;i<=N;i+=2)isprime[i]=false;
  13. prime.push_back(2);
  14. for(i=3;i<=m;i+=2)
  15. {
  16. if(isprime[i])
  17. {
  18. for(j=i*i;j<N;j+=i)
  19. {
  20. isprime[j]=0;
  21. }
  22. prime.push_back(i);
  23. }
  24. }
  25. for(i=m;i<=N;i++)
  26. {
  27. if(isprime[i])prime.push_back(i);
  28. }
  29. }
  30. int main()
  31. {
  32. fastread();
  33. primefactor();
  34. int n,i;
  35. while(scanf("%d",&n))
  36. {
  37. if(n==0)break;
  38. else if(isprime[n])printf("0\n");
  39. else
  40. {
  41. i=upper_bound(prime.begin(),prime.end(),n)-prime.begin();
  42. printf("%d\n",prime[i]-prime[i-1]);
  43. }
  44. }
  45. return 0;
  46. }
RAW Paste Data