Advertisement
Farjana_akter

Untitled

May 30th, 2020
49
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.64 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int ll;
  4. #define MAX 320000
  5. bool mark[MAX+5];
  6. vector<ll>isprime;
  7.  
  8. void sieve()
  9. {
  10. ll i,j;
  11. mark[0]=true;
  12. mark[1]=true;
  13. for(i=2;i*i<=MAX;i++)
  14. {
  15. if(mark[i]==false)
  16. {
  17. for(j=i*i;j<=MAX;j+=i)
  18. mark[j]=true;
  19. }
  20. }
  21. for(i=2;i<=MAX;i++)
  22. if(mark[i]==false)
  23. isprime.push_back(i);
  24. }
  25.  
  26.  
  27. void segsieve(ll l,ll r)
  28. {
  29. ll prime[r-l+1+5],i,j;
  30. for(i=0;i<r-l+1;i++)
  31. prime[i]=false;
  32. if(l==1)prime[0]=true;
  33. for(i=0;isprime[i]*isprime[i]<=r;i++)
  34. {
  35. ll curprime=isprime[i];
  36. ll base=(l/curprime)*curprime;
  37. if(base<l)
  38. base+=curprime;
  39. for(j=base;j<=r;j+=curprime)
  40. {
  41. prime[j-l]=true;
  42. }
  43. if(base==curprime)
  44. prime[base-l]=false;
  45. }
  46. vector<ll>v;
  47. for(i=0;i<r-l+1;i++){
  48. if(prime[i]==false){
  49. v.push_back(i+l);
  50. }
  51. }
  52. ll mn=1e10,mx=0,c1,c2,d1,d2;
  53. for(i=1;i<v.size();i++)
  54. {
  55. ll diff=v[i]-v[i-1];
  56. if(diff>mx)
  57. {
  58. mx=diff;
  59. d1=v[i-1];
  60. d2=v[i];
  61. }
  62. if(diff<mn)
  63. {
  64. mn=diff;
  65. c1=v[i-1];
  66. c2=v[i];
  67. }
  68. }
  69. if(mx==0 || mn==1e10)
  70. cout<<"There are no adjacent primes."<<endl;
  71. else
  72. cout<<c1<<","<<c2<<" are closest, "<<d1<<","<<d2<<" are most distant."<<endl;
  73. }
  74.  
  75. int main()
  76. {
  77. sieve();
  78. ll t,i,j,k,l,r;
  79. while(cin>>l>>r)
  80. {
  81. segsieve(l,r);
  82. }
  83. return 0;
  84. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement