NgJaBach

Gay Prime

Feb 19th, 2020
144
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.80 KB | None
  1. #include<iostream>
  2. typedef long long ll;
  3. using namespace std;
  4. void segmented_prime(){
  5.     const ll ok=2;
  6.     ll p,i,j,n,a,b,t;
  7.     scanf("%lld",&t);
  8.     for(p=0;p<t;++p){
  9.         scanf("%lld %lld", &a, &b);
  10.         n=b-a+1;
  11.         bool sieve[n];
  12.         for(i=0;i<n;++i) sieve[i]=true;
  13.         for(i=2;i*i<=b;++i){
  14.             for(j=max(i*i,(a+(i-1))/i*i);j<=b;j+=i){
  15.                 sieve[j-a]=false;
  16.             }
  17.         }
  18.         for(i=max(a,ok);i<=b;++i){
  19.             if(sieve[i-a]) printf("%lld\n",i);
  20.         }
  21.     }
  22. }
  23. void eratosthenes(){
  24.     ll i,p,j,n,t;
  25.     cin>>t;
  26.     for(p=0;p<t;++p){
  27.         cin>>n;
  28.         bool sieve[n+1];
  29.         for(i=1;i<=n;++i) sieve[i]=true;
  30.         for(i=2;i<=n;++i){
  31.             if(sieve[i]){
  32.                 cout<<i<<endl;
  33.                 for(j=2*i;j<=n;j+=i) sieve[j]=false;
  34.             }
  35.         }
  36.     }
  37. }
  38. void linear_sieve(){
  39.     int i,j,n,pr[N];
  40.     vector<int>ans;
  41.     cin>>n;
  42.     for(i=2;i<=n;++i){
  43.         if(pr[i]==0){
  44.             pr[i]=i;
  45.             ans.push_back(i);
  46.         }
  47.         for(j=0;j<ans.size();++j){
  48.             if(i*ans[j]>n) break;
  49.             if(ans[j]>pr[i]) break;
  50.             pr[i*ans[j]]=ans[j];
  51.         }
  52.     }
  53.     for(i=0;i<ans.size();++i) cout<<ans[i]<<" ";
  54. }
  55. int main(){
  56.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  57. //  segmented_prime();
  58. //  eratosthenes();
  59. //  linear_sieve();
  60. }
RAW Paste Data Copied