Print primes till 1e9 fast.

→ Pay attention

Before contest
Refact.ai Match 1 (Codeforces Round 985)
4 days
Register now »

*has extra registration

→ Top rated

#	User	Rating
1	tourist	4009
2	jiangly	3831
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	gamegame	3386
10	ksun48	3373

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

View all →

→ Find user

→ Recent actions

Detailed →

potter's blog

Print primes till 1e9 fast.

By potter, history, 3 years ago, In English

I have tried sieve and segmented sieve too but they are slow. Can anyone provide code to print primes till 10^9 FAST?

Python code would be a great help.

potter
3 years ago
9

Comments (5)

Show archived | Write comment?

SPyofgame

3 years ago, # |

← Rev. 3 →

AFAIK, just using sieve to count prime upto 1e9 is already 600ms for fasted code I known (run on GNU G++17 7.3.0 CF 23/9/2021). Taking all primes $$$\leq 10^9$$$ is already 4-5 seconds ($$$50,847,534$$$ numbers).

Assuming your " FAST " mean 1 second then I would like to say it must be very heavily micro-optimized for each operation to do so.

But enumerate through all prime $$$\leq 10^9$$$ under 1 second is possible if you manage to maintain the prime array for each range

→ Reply

clyring

3 years ago, # ^ |

600ms seems quite fast if the sieve is actually generating all of the primes in that range and not using number theory magic to count them in $$$o(n)$$$. Care to share? I tried writing a somewhat optimized segmented sieve in Haskell in response to this blog's now-deleted predecessor, getting generation down to about 1.7 seconds and generation+printing down to about 2.8 seconds. My code seemed to get mangled when I tried to insert it into this comment (probably due its use of $ interacting poorly with MathJax), so here it as a submission link: 141417208. The quoted times above are from Custom Invocation with input 1000000000 240000 1200.

I estimate the printing alone would take about 2 seconds, and I'm not aware of any integer output template in any language that's appreciably faster than the one I use in my Haskell code, so 1 second for generation+printing might be infeasible. But obviously an un-fused lazy singly-linked list is not a very efficient data structure to hold 50 million Ints in (it would be over 2GB if it existed in memory all at once...), and I don't think GHC is very good at optimizing this kind of array-heavy code, so maybe it's possible to actually generate the primes a good deal faster than I do.

→ Reply

SPyofgame

3 years ago, # ^ |

Well I just use my own modified version from Bitwise Segment Sieve from prime sieve github (which some bitwise wheel sieve precalculation) that specifically sieve for int $$$\leq 10^9$$$. If just to count number then it is fast but if to collect all prime numbers then it is much slower than Non-bitwise one.

The code 23 and 24 are lost during the covid but I think it still being saved somewhere in my old computer. Yet I will try to remake a new one if possible.

The blog I am writing is not completed, but you can see the code

1 - Brute-forces

#include <iostream>

using namespace std;

const int LIM = 1e6;

bool checkPrime(int n)
{
    int cnt = 0;
    for (int d = 1; d <= n; ++d)
        if (n % d == 0)
            ++cnt;

    return cnt == 2;
}

int cntPrime;
bool isPrime[LIM + 1];
void sieve(int n)
{
    cntPrime = 0;
    for (int x = 0; x <= n; ++x)
    {
        if (checkPrime(x))
        {
            ++cntPrime;
            isPrime[x] = true;
        }
    }
}

int main()
{
    int n;
    cin >> n;

    sieve(n);
    cout << "Number of primes up to " << n << " is " << cntPrime;
    return 0;
}

2.Trial Division

#include <iostream>

using namespace std;

const int LIM = 1e6;

bool checkPrime(int n)
{
    if (n <= 1) return false;
    for (int d = 2; d * d <= n; ++d)
        if (n % d == 0)
            return false;
            
    return true;
}

int cntPrime;
bool isPrime[LIM + 1];
void sieve(int n)
{
    cntPrime = 0;
    for (int x = 0; x <= n; ++x)
    {
        if (checkPrime(x))
        {
            ++cntPrime;
            isPrime[x] = true;
        }
    }
}

int main()
{
    int n;
    cin >> n;

    sieve(n);
    cout << "Number of primes up to " << n << " is " << cntPrime;
    return 0;
}

3.Improved Trial Division

#include <iostream>
#include <cstring>

using namespace std;

const int LIM = 1e6;

bool checkPrime(int n)
{
    if (n <= 1) return false;
    if (n == 2 || n == 3 || n == 5) return true;
    if (n % 2 == 0 || n % 3 == 0 || n % 5 == 0) return false;

    for (int d = 5; d * d <= n; d += 6)
    {
        if (n % d == 0) return false;
        if (n % (d + 2) == 0) return false;
    }

    return true;
}

int cntPrime;
bool isPrime[LIM + 1];
void sieve(int n)
{
    memset(isPrime, false, sizeof(isPrime));
    isPrime[2] = isPrime[3] = true;

    cntPrime = (n >= 2) + (n >= 3);
    for (int x = 5; x <= n; x += 6)
    {
        if (checkPrime(x))
        {
            ++cntPrime;
            isPrime[x] = true;
        }

        if (checkPrime(x + 2))
        {
            ++cntPrime;
            isPrime[x + 2] = true;
        }
    }
}

int main()
{
    int n;
    cin >> n;

    sieve(n);
    cout << "Number of primes up to " << n << " is " << cntPrime;
    return 0;
}

4.Second Improved Trial Division

#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>

using namespace std;

typedef unsigned int uint;

const int LIM = 1e6;

int cntPrime;
int prime[LIM + 1];
void sieve(int n)
{
    cntPrime = 0;
    if (n < 2) return ;
    prime[cntPrime++] = 2;
    if (n < 3) return ;
    prime[cntPrime++] = 3;
    
    int sqrtn = 3, tickn = 1;
    for (int x = 5, t = 1; x <= n; x += 2 + 2 * (t ^= 1))
    {
        bool ok = true;
        for (int i = 0; i < cntPrime && prime[i] <= sqrtn; ++i)
        {
            if (x % prime[i] == 0) 
            {
                ok = false;
                break;
            }
        }
        
        if (ok) prime[cntPrime++] = x;
        if (--tickn == 0) tickn = sqrtn++;
        if (t && --tickn == 0) tickn = sqrtn++;
    }
}

int main()
{
    int n;
    cin >> n;

    sieve(n);
    cout << "Number of primes up to " << n << " is " << cntPrime;
    return 0;
}

5.Divisor Sieve

#include <iostream>
#include <cstring>

using namespace std;

const int LIM = 1e6;

int cntPrime;
bool isPrime[LIM + 1];
void sieve(int n)
{
    memset(isPrime, true, sizeof(isPrime[0]) * (n + 1));
    isPrime[0] = isPrime[1] = false;

    for (int p = 2; p * p <= n; ++p)
        for (int v = 2; p * v <= n; ++v) 
            isPrime[p * v] = false;

    cntPrime = 0;
    for (int p = 0; p <= n; ++p) cntPrime += isPrime[p];
}

int main()
{
    int n;
    cin >> n;

    sieve(n);
    cout << "Number of primes up to " << n << " is " << cntPrime;
    return 0;
}

6.Sundaram Sieve

#include <iostream>
#include <cstring>

using namespace std;

const int LIM = 1e6;

int cntPrime;
bool isPrime[LIM / 2 + 1];
void sieve(int n)
{ 
    int k = (n - 2) / 2; 
    memset(isPrime, true, sizeof(isPrime[0]) * (k + 1));
    isPrime[0] = false;
    
    for (int i = 1; i * i <= n; ++i)
        for (int j = i; i + j + 2 * i * j <= k; ++j)
                isPrime[i + j + 2 * i * j] = false;
    
    cntPrime = 1;
    for (int i = 1; i <= k; ++i) 
        if (isPrime[i] == true) /// prime 2 * i + 1
            ++cntPrime;
}

int main()
{
    int n;
    cin >> n;

    sieve(n);
    cout << "Number of primes up to " << n << " is " << cntPrime;
    return 0;
}

7.Eratosthenes Sieve

#include <iostream>
#include <cstring>

using namespace std;

const int LIM = 1e6;

int cntPrime;
bool isPrime[LIM + 1];
void sieve(int n)
{
    memset(isPrime, true, sizeof(isPrime[0]) * (n + 1));
    isPrime[0] = isPrime[1] = false;

    for (int p = 2; p * p <= n; ++p) if (isPrime[p])
        for (int x = p + p; x <= n; x += p) 
            isPrime[x] = false;

    cntPrime = 0;
    for (int p = 0; p <= n; ++p) cntPrime += isPrime[p];
}

int main()
{
    int n;
    cin >> n;

    sieve(n);
    cout << "Number of primes up to " << n << " is " << cntPrime;
    return 0;
}

8.Improved Eratosthenes Sieve

#include <iostream>
#include <cstring>

using namespace std;

const int LIM = 1e6;

int cntPrime;
bool isPrime[LIM + 1];
void sieve(int n)
{
    memset(isPrime, true, sizeof(isPrime[0]) * (n + 1));
    isPrime[0] = isPrime[1] = false;

    for (int p = 4; p <= n; p += 2) isPrime[p] = false;
    for (int p = 3; p * p <= n; p += 2) if (isPrime[p])
        for (int x = p * p; x <= n; x += p) 
            isPrime[x] = false;

    cntPrime = (n >= 2);
    for (int p = 3; p <= n; p += 2) cntPrime += isPrime[p];
}

int main()
{
    int n;
    cin >> n;

    sieve(n);
    cout << "Number of primes up to " << n << " is " << cntPrime;
    return 0;
}

9.Linear Eratosthenes Sieve

#include <iostream>
#include <vector>

using namespace std;

const int LIM = 1e6;

vector<int> prime;
vector<int> lpf;
void sieve(int n)
{
    prime.assign(1, 2);
    lpf.assign(n + 1, 2);

    for (int x = 3; x <= n; x += 2)
    {
        if (lpf[x] == 2) prime.push_back(lpf[x] = x);
        for (int i = 0; i < prime.size() && prime[i] <= lpf[x] && prime[i] * x <= n; ++i)
            lpf[prime[i] * x] = prime[i];
    }
}

int main()
{
    int n;
    cin >> n;

    sieve(n);
    cout << "Number of primes up to " << n << " is " << prime.size();
    return 0;
}

10.Improved Linear Eratosthenes Sieve

#include <iostream>
#include <vector>

using namespace std;

const int LIM = 1e6;
const int LIM_P = 664579 + 66;
 
int cntPrime;
int prime[LIM_P];
int lpf[LIM + 1];
void sieve(int n)
{
    cntPrime = 0;
    prime[cntPrime++] = 2;
    fill_n(lpf, n + 1, 2);

    for (int x = 3; x <= n; x += 2)
    {
        if (lpf[x] == 2) prime[cntPrime++] = (lpf[x] = x);
        for (int i = 0; i < cntPrime && prime[i] <= lpf[x] && prime[i] * x <= n; ++i)
            lpf[prime[i] * x] = prime[i];
    }
}

int main()
{
    int n;
    cin >> n;

    sieve(n);
    cout << "Number of primes up to " << n << " is " << cntPrime;
    return 0;
}

11.Atkin Sieve

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>

using namespace std;

const int LIM = 1e6;

int cntPrime = 0;
bool isPrime[LIM + 1];
void sieve(int n)
{ 
    memset(isPrime, false, sizeof(isPrime));
    if (n < 2) return ;
    isPrime[2] = true; cntPrime = 1;
    if (n < 3) return ;
    isPrime[3] = true; cntPrime = 2;
    if (n < 4) return ;

    for (int x = 1; x * x <= n; ++x)
    { 
        int A = x * x;
        for (int y = 1; y * y <= n - A; ++y)
        {
            int B = y * y, p;
            if (p = 4 * A + B, p <= n && (p % 12 == 1 || p % 12 == 5)) isPrime[p] = !isPrime[p]; 
            if (p = 3 * A + B, p <= n && p % 12 == 7)                  isPrime[p] = !isPrime[p]; 
            if (p = 3 * A - B, p <= n && p % 12 == 11 && x > y)        isPrime[p] = !isPrime[p]; 
        } 
    } 
  
    int rn = sqrt(n);
    for (int x = 5; x <= rn; ++x) if (isPrime[x])
        for (int k = 1; k * x * x <= n; ++k)
            isPrime[k * x * x] = false;
    
    cntPrime = count(isPrime, isPrime + n + 1, 1);
}

int main()
{
    int n;
    cin >> n;

    sieve(n);
    cout << "Number of primes up to " << n << " is " << cntPrime;
    return 0;
}

12.Improved Atkin Sieve

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>

using namespace std;

const int LIM = 1e6;

int cntPrime;
bool isPrime[LIM + 1];
void sieve(int n)
{ 
    memset(isPrime, false, sizeof(isPrime));
    if (n < 2) return ;
    isPrime[2] = true; cntPrime = 1;
    if (n < 3) return ;
    isPrime[3] = true; cntPrime = 2;
    if (n < 4) return ;
    
    for (int upx = sqrt(n / 4) + 1, x = 1; x <= upx; ++x)
    { 
        int X = 4 * x * x;
        for (int upy = sqrt(n - X), y = 1; y <= upy; ++y)
        {   
            int p = X + y * y; 
            if (p % 12 == 1 || p % 12 == 5) 
                isPrime[p] = !isPrime[p]; 
        } 
    }

    for (int upx = sqrt(n / 3) + 1, x = 1; x <= upx; x += 2)
    { 
        int t = 1;
        int X = 3 * x * x;
        for (int upy = sqrt(n - X), y = 2; y <= upy; y += 6)
        {   
            int p = X + y * y; 
            isPrime[p] = !isPrime[p]; 
        } 
        
        for (int upy = sqrt(n - X), y = 4; y <= upy; y += 6)
        {   
            int p = X + y * y; 
            isPrime[p] = !isPrime[p]; 
        } 
    }

    for (int rn = sqrt(n), x = 1; x <= rn; ++x)
    {
        int X = 3 * x * x;
        for (int y = max(int(sqrt(X - n)) + 1, 1); y < x; ++y)
        {
            int p = X - y * y;
            if (p % 12 == 11)
                isPrime[p] = !isPrime[p];
        }
    }

    int rn = sqrt(n);
    for (int i = 5; i <= rn; i += 2) if (isPrime[i])
        for (int t = i * i, j = t; j < n; j += t)
            isPrime[j] = false;

    for (int i = 5; i <= n; i += 2)
        if (isPrime[i])
            ++cntPrime;
}

int main()
{
    int n;
    cin >> n;

    sieve(n);
    cout << "Number of primes up to " << n << " is " << cntPrime;
    return 0;
}

13.Non-modulo Atkin Sieve

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>

using namespace std;

constexpr int LIM = 1e6;

int cntPrime;
bool isPrime[LIM + 1];

void sieve(int n)
{   
    memset(isPrime, false, sizeof(isPrime));
    if (n < 2) return ;
    isPrime[2] = true; cntPrime = 1;
    if (n < 3) return ;
    isPrime[3] = true; cntPrime = 2;
    if (n < 4) return ;
    
    for (int upx = sqrt(n / 4) + 1, x = 1; x <= upx; ++x)
    { 
        int X = 4 * x * x;
        int t = 0;
        int b = (x % 3 == 0);
        for (int y = 1, p = X + y * y; p <= n; y += 2 + (b ? 2 * (t ^= 1) : 0), p = X + y * y)
            isPrime[p] = !isPrime[p];
    }

    for (int upx = sqrt(n / 3) + 1, x = 1; x <= upx; x += 2)
    { 
        int t = 1;
        int X = 3 * x * x;
        for (int y = 2, p = X + y * y; p <= n; y += 2 + 2 * (t ^= 1), p = X + y * y)
            isPrime[p] = !isPrime[p];
    }

    for (int rn = sqrt(n), x = 1; x <= rn; ++x)
    {
        int X = 3 * x * x;
        int t = x & 1;
        for (int y = 1 + t, p = X - y * y; y < x; y += 2 + 2 * (t ^= 1))
        {
            p = X - y * y;
            if (p <= n) isPrime[p] = !isPrime[p];
        }
    }
    
    int rn = sqrt(n);
    for (int i = 5; i <= rn; i += 2) if (isPrime[i])
        for (int t = i * i, j = t; j < n; j += t)
            isPrime[j] = false;

    for (int i = 5; i <= n; i += 2)
        if (isPrime[i])
            ++cntPrime;
}

int main()
{
    int n;
    cin >> n;

    sieve(n);
    cout << "Number of primes up to " << n << " is " << cntPrime;
    return 0;
}

14.Improved Non-modulo Atkin Sieve

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>

using namespace std;

constexpr int LIM = 1e6;
constexpr int offset[2] = {2, 4};
constexpr int n3[3] = {1, 2, 0};


int cntPrime;
bool isPrime[LIM + 1];

void sieve(int n)
{ 
    memset(isPrime, false, sizeof(isPrime));
    if (n < 2) return ;
    isPrime[2] = true; cntPrime = 1;
    if (n < 3) return ;
    isPrime[3] = true; cntPrime = 2;
    if (n < 4) return ;
    
    for (int upx = sqrt(n / 4) + 1, x = 1, x3 = 1, X = 4; x <= upx; ++x, x3 = n3[x3], X = 4 * x * x)
    {
        bool t = false;
        for (int y = 1, p = X + y * y; p <= n; y += (x3 ? 2 : offset[t ^= 1]), p = X + y * y)
            isPrime[p] = !isPrime[p];
    }

    for (int upx = sqrt(n / 3) + 1, x = 1, X = 3; x <= upx; x += 2, X = 3 * x * x)
    {
        bool t = true;
        for (int y = 2, p = X + y * y; p <= n; y += offset[t ^= 1], p = X + y * y)
            isPrime[p] = !isPrime[p];
    }
        
    // This code is slightly faster
    for (int rn = sqrt(n), x = 1, X = 3, v = 2, T = 1; x <= rn; ++x, X = 3 * x * x)
    {
        while (T * T <= X - n) ++T;
        bool t = x & 1;
        int y = 1 + t;
        if (X - y * y > n) y += (T - y) / 6 * 6;
        while (X - y * y > n) y += offset[t ^= 1];
        for (int p = X - y * y; y < x; y += offset[t ^= 1], p = X - y * y)
            isPrime[p] = !isPrime[p];
    }

    bool t = 1;
    int rn = sqrt(n);
    for (int x = 5; x <= rn; x += offset[t ^= 1]) if (isPrime[x])
        for (int t = x * x, p = t; p <= n; p += t)
            isPrime[p] = false;
            
    for (int x = 5; x <= n; x += 6)
        cntPrime += isPrime[x] + isPrime[x + 2]; /// x is Prime or/and (x + 2) is Prime
}

int main()
{
    int n;
    cin >> n;

    sieve(n);
    cout << "Number of primes up to " << n << " is " << cntPrime;
    return 0;
}

15.Eratosthenes Wheel-2 Sieve

#include <iostream>
#include <cstring>

using namespace std;

const int LIM = 1e6;

int cntPrime;
bool isPrime[LIM / 2 + 1];
void sieve(int n)
{
    memset(isPrime, true, sizeof(isPrime[0]) * (n / 2 + 1));
    isPrime[0 / 2] = isPrime[1 / 2] = false;

    for (int p = 2; p * p <= n; ++p) if (isPrime[p / 2])
        for (int x = p + p; x <= n; x += p) if (x % 2 == 1)
            isPrime[x / 2] = false;

    cntPrime = (n >= 2);
    for (int p = 3; p <= n; p += 2) if (isPrime[p / 2]) cntPrime += isPrime[p / 2];
}

int main()
{
    int n;
    cin >> n;

    sieve(n);
    cout << "Number of primes up to " << n << " is " << cntPrime;
    return 0;
}

16.Improved Eratosthenes Wheel-2 Sieve

#include <iostream>
#include <cstring>

using namespace std;

const int LIM = 1e6;

int cntPrime;
bool isPrime[LIM / 2 + 1];
void sieve(int n)
{
    memset(isPrime, true, sizeof(isPrime[0]) * (n / 2 + 1));
    isPrime[0] = false;

    for (int p = 3; p * p <= n; p += 2) if (isPrime[p >> 1])
        for (int x = p + p + p; x <= n; x += 2 * p) 
            isPrime[x >> 1] = false;

    cntPrime = (n >= 2) + (n >= 3);
    for (int p = 5; p <= n; p += 6) cntPrime += isPrime[p >> 1] + isPrime[(p + 2) >> 1];
}

int main()
{
    int n;
    cin >> n;

    sieve(n);
    cout << "Number of primes up to " << n << " is " << cntPrime;
    return 0;
}

17.Eratosthenes Wheel-2 Bitwise Sieve

#include <iostream>
#include <bitset>

using namespace std;

const int LIM = 1e6;

int cntPrime;
bitset<LIM / 2 + 1> isNotPrime;
void sieve(int n)
{
    isNotPrime[0] = true;
    for (int p = 3; p * p <= n; p += 2) if (!isNotPrime[p >> 1])
        for (int x = p * p; x <= n; x += 2 * p) 
            isNotPrime[x >> 1] = true;

    cntPrime = (n >= 2);
    for (int p = 3; p <= n; p += 2) cntPrime += !isNotPrime[p >> 1];
}

int main()
{
    int n;
    cin >> n;

    sieve(n);
    cout << "Number of primes up to " << n << " is " << cntPrime;
    return 0;
}

18.Improved Eratosthenes Wheel-2 Bitwise Sieve

#include <iostream>
#include <bitset>

using namespace std;

typedef unsigned int uint;
const uint LIM = 1e6;

uint cntPrime;
uint isNotPrime[(LIM >> 5) / 2 + 3];
uint get(uint p) { return (isNotPrime[p >> 5] >> (p & 31)) & 1; }
void set(uint p) { isNotPrime[p >> 5] |= 1 << (p & 31); }
void sieve(uint n)
{
    isNotPrime[0] = true;
    for (uint p = 3; p * p <= n; p += 2) if (!get(p >> 1))
        for (uint x = p * p; x <= n; x += 2 * p) 
            set(x >> 1);

    cntPrime = (n >= 2) + (n >= 3);
    for (uint p = 5; p <= n; p += 6) cntPrime += !get(p >> 1) + !get((p + 2) >> 1);
}

int main()
{
    int n;
    cin >> n;

    sieve(n);
    cout << "Number of primes up to " << n << " is " << cntPrime;
    return 0;
}

19.Improved Erastothenes Wheel-2-3-5-7 Sieve

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>

using namespace std;

#define all(x) (x).begin(), (x).end()

const int LIM = 100000000;
bool isPrime[(LIM + 1 - 7) / 2];

typedef unsigned int uint;

constexpr uint WHEEL_1[] = {2, 1, 2, 1, 2, 3, 1, 3};
constexpr uint WHEEL_0[] = {1, 0, 1, 0, 1, 2, 0, 2};
constexpr uint NEXT8[] =   {1, 2, 3, 4, 5, 6, 7, 0};

uint cntPrime;
void sieve(uint n)
{
    cntPrime = 0u; if (n < 2u) return ;
    cntPrime = 1u; if (n < 3u) return ;
    cntPrime = 2u; if (n < 5u) return ;
    cntPrime = 3u; if (n < 7u) return ;

    uint length = (n - 7u) / 2u;
    uint sqrt_lim = (sqrt(n) - 7u) / 2u;
    memset(isPrime, true, sizeof(isPrime[0]) * (length + 1));
    for (uint i = 0u, w = 0u; i <= sqrt_lim; i += WHEEL_1[w], w = NEXT8[w]) if (isPrime[i])
    {
        uint p = 7u + i + i;
        uint pa[] = {p, p + p, p + p + p};
        for (uint j = (p * p - 7) / 2, m = w; j <= length; j += pa[WHEEL_0[m]], m = NEXT8[m])
            isPrime[j] = false;
    }
    for (uint i = 0, w = 0; i <= length; i += WHEEL_1[w], w = NEXT8[w]) if (isPrime[i]) ++cntPrime; /// 7 + i + i is Prime
}

int main()
{
    int n;
    cin >> n;

    sieve(n);
    cout << "Number of primes up to " << n << " is " << cntPrime;
    return 0;
}

20.Improved Erastothenes Wheel-2-3-5-7 Segment Sieve

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>

using namespace std;

typedef unsigned int uint;

constexpr uint LIM = 1e6;
constexpr uint NEXT8[] = {1, 2, 3, 4, 5, 6, 7, 0};
constexpr uint WHEEL_1[] = {2, 1, 2, 1, 2, 3, 1, 3}; 
constexpr uint WHEEL_0[] = {1, 0, 1, 0, 1, 2, 0, 2}; 
constexpr uint WHEEL_POS[] = {0, 2, 3, 5, 6, 8, 11, 12};
constexpr uint WHEEL_IDX[] = {0, 0, 1, 2, 2, 3, 4, 4, 5, 5, 5, 6, 7, 7, 7, 0, 0, 1, 2, 2, 3, 4, 4, 5, 5, 5, 6, 7};
constexpr uint WHEEL_DUP[] = {0, 2, 2, 3, 5, 5, 6, 8, 8, 11, 11, 11, 12, 15, 15, 15, 17, 17, 18, 20, 20, 21, 23, 23, 26, 26, 26, 27};
constexpr uint L1CACHEPOW = 14u + 3u;
constexpr uint L1CACHESZ = (1u << (int)L1CACHEPOW); 
constexpr uint SEGSZ = L1CACHESZ / 15u * 15u;                              
constexpr uint PRESZ = (65535u - 7u) / 2u;
bool isPrime[PRESZ + 1];
bool segPrime[SEGSZ];

uint cntPrime;
void sieve(uint n)
{
    cntPrime = 0u; if (n < 2u) return;
    cntPrime = 1u; if (n < 3u) return;
    cntPrime = 2u; if (n < 5u) return;
    cntPrime = 3u; if (n < 7u) return;

    const uint upper = (n - 7u) / 2u; 
    uint sqrt_upper = (sqrt(n) - 7u) / 2u;
    memset(isPrime, true, sizeof(isPrime));
    for (uint i = 0u; i <= 124u; ++i) if (isPrime[i])
    {
        uint p = 7u + i + i; 
        for (uint j = (p * p - 7u) / 2u; j <= PRESZ; j += p)
            isPrime[j] = false;
    }
    
    for (uint i = 0u, w = 0u, si = 0u; i <= upper; i += WHEEL_1[w], si += WHEEL_1[w], si = (si >= SEGSZ) ? 0u : si, w = NEXT8[w])
    {
        if (si == 0u)
        {
            memset(segPrime, true, sizeof(segPrime));
            for (uint j = 0u, bw = 0u; j <= PRESZ; j += WHEEL_1[bw], bw = NEXT8[bw]) if (isPrime[j])
            {
                uint p = 7u + j + j;
                uint k = p * (j + 3u) + j;
                if (k >= i + SEGSZ) break;
                uint pa[3] = {p, p + p, p + p + p};
                uint sw = bw;
                if (k < i)
                {
                    k = (i - k);
                    k %= (15u * p);
                    if (k != 0)
                    {
                        uint os = WHEEL_POS[bw];
                        sw = os + ((k + p - 1u) / p);
                        sw = WHEEL_DUP[sw];
                        k = (sw - os) * p - k;
                        sw = WHEEL_IDX[sw];
                    }
                }
                else k -= i;

                for (; k < SEGSZ; k += pa[WHEEL_0[sw]], sw = NEXT8[sw])
                    segPrime[k] = false;
            }
        }

        if (segPrime[si]) ++cntPrime; /// 7 + i + i is Prime
    }
}

int main()
{
    int n;
    cin >> n;

    sieve(n);
    cout << "Number of primes up to " << n << " is " << cntPrime;
    return 0;
}

21.Erastothenes Segment Sieve

#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>

using namespace std;

const int LIM = 1e6;
const int SQRT_LIM = sqrt(LIM);
bool isPrime[SQRT_LIM + 1];

int cntPrime;
void sieve(int n)
{
    int LIM = floor(sqrt(n));
    
    vector<int> prime;
    memset(isPrime, true, sizeof(isPrime[0]) * LIM);
    for (int p = 2; p * p <= LIM; ++p) if (isPrime[p] == true)
        for (int x = p + p; x <= LIM; x += p)
            isPrime[x] = false;
    
    cntPrime = 0;
    for (int p = 2; p <= LIM; ++p) if (isPrime[p])
    {
        ++cntPrime;
        prime.push_back(p);
    }

    for (int low = LIM; low <= n; low += LIM)
    {
        int high = min(n, low + LIM);
        memset(isPrime, true, sizeof(isPrime[0]) * LIM);

        for (int i = 0; i < prime.size(); ++i)
        {
            int p = (low + prime[i] - 1) / prime[i] * prime[i];
            for (int x = p; x <= high; x += prime[i])
                isPrime[x - low] = false;
        }
 
        for (int n = low; n < high; ++n)
            if (isPrime[n - low] == true)
                ++cntPrime;
    }
}

int main()
{
    int n;
    cin >> n;

    sieve(n);
    cout << "Number of primes up to " << n << " is " << cntPrime;
    return 0;
}

22.Improved Erastothenes Segment Sieve


#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>

using namespace std;

#define all(x) (x).begin(), (x).end()

const int LIM = 1e6;
const int OPTIMAL_RANGE = 1 << 15;
const int offset[2] = {2, 4};

int cntPrime;
bool mark[OPTIMAL_RANGE];
bool isPrime[OPTIMAL_RANGE];
int seg_prime[OPTIMAL_RANGE];
int seg_multi[OPTIMAL_RANGE];

void sieve(int lim)
{
    if (lim < 2) return ;
    int sqrt = std::sqrt(lim);
    int segment_size = max(sqrt, OPTIMAL_RANGE);
    
    memset(isPrime, true, sizeof(isPrime));
    cntPrime = (lim >= 2) + (lim >= 3);
    int qdrt = std::sqrt(sqrt);
    for (int x = 5, t = 0; x <= qdrt; x += offset[t ^= 1]) if (isPrime[x])
        for (int p = x * x; p <= sqrt; p += x)
            isPrime[p] = false;

    int n_seg = 0;
    int s = 5, n = 5;
    bool tn = 1, ts = 1;
    for (int low = 0; low <= lim; low += segment_size)
    {
        int high = min(low + segment_size - 1, lim);
        memset(mark, true, sizeof(mark[0]) * (high - low + 1));

        for (; s * s <= high; s += offset[ts ^= 1]) if (isPrime[s])
        {
            seg_prime[n_seg] = s;
            seg_multi[n_seg] = s * s - low;
            ++n_seg;
        }

        for (int x = 0; x < n_seg; ++x) 
        {
            int p = seg_multi[x];
            for (int k = seg_prime[x] * 2; p < segment_size; p += k) mark[p] = false;
            seg_multi[x] = p - segment_size;
        }

        for (; n <= high; n += offset[tn ^= 1])
            if (mark[n - low]) 
                ++cntPrime;
    }
}

int main()
{
    int n;
    cin >> n;

    sieve(n);
    cout << "Number of primes up to " << n << " is " << cntPrime;
    return 0;
}

23.Erastothenes Segment Bitwise Sieve

Lost the original files.

→ Reply

duzinho039

15 months ago, # |

-8

You can just use the normal sieve to print all she primes upto 1e9 which takes about 5 seconds than copy the primes (which are about 3000) and hard-code them in a vector. Then you don't have to calculate them in the actual submission

→ Reply

Libert995

4 months ago, # ^ |

thanks worked for me

→ Reply