fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4.  
  5. ll a, b, ct;
  6.  
  7. void seg_sieve(ll myPrimes[])
  8. {
  9.     bool isPrime[b+1];
  10.     memset(isPrime, 1, sizeof isPrime); //at first all are primes up to b
  11.     for(ll i = 2; i*i<=b; i++)
  12.     {
  13.         if(isPrime[i])
  14.         {
  15.             for(ll j = i; i*j<=b; j+=i)
  16.                 isPrime[i*j] = 0;
  17.         }
  18.     }
  19.     ll pre[b+1];
  20.     ct = 0;
  21.     for(int i = 2; i*i<=b; i++) //store primes up to sqrt(b) for further calculation in segmented sieve
  22.     {
  23.         if(isPrime[i])
  24.             pre[ct++] = i;
  25.     }
  26.     ll s, p;
  27.     // at first all numbers are considered to be prime from a to b.
  28.     for(ll i = a; i<=b; i++)
  29.         isPrime[i] = 1;
  30.     for(ll i = 0; i<ct; i++)
  31.     {
  32.         p = pre[i];
  33.         s = a/p;    //divide by 2, 3, 5, 7 up to sqrt(b)
  34.         s = s*p;    //multiply by 2, 3, 7 and so on up to sqrt(b)
  35.         for(ll j = s; j<=b; j+=p)
  36.         {
  37.             if(j<a)
  38.                 continue;
  39.             isPrime[j] = 0;
  40.         }
  41.     }
  42.     ct = 0;
  43.     for(ll i = a; i<=b; i++)
  44.     {
  45.         if(isPrime[i])
  46.             myPrimes[ct++] = i;
  47.     }
  48. }
  49.  
  50. int main()
  51. {
  52.     cin>>a>>b;
  53.     ll myPrimes[b+1];
  54.     seg_sieve(myPrimes);
  55.     for(ll i = 0; i<ct; i++)
  56.         cout<<myPrimes[i]<<" ";
  57.     return 0;
  58. }
  59.  
Success #stdin #stdout 0s 16064KB
comments (?)
stdin
copy 
10 20
stdout
copy 
11 13 17 19
https://ideone.com/LNPuBB
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

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!