user140242

# segmented wheel sieve python

import time
import numpy as np
from math import isqrt

def segmented_wheel_sieve(n , max_bW):
    dim_seg = 2**22
    bW = 30
    n_PB = 3

user140242

///     This is a implementation of the bit wheel segmented sieve 
///     multithreaded with OpenMP (compile with -fopenmp option)
///     with max base wheel size choice  30 , 210 , 2310 - user140242


#include <iostream>
#include <cmath>
#include <vector>
#include <cstdlib>
#include <stdint.h>

user140242

// Lucas-Lehmer Primality Test

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <cstdlib>
#include <stdint.h>

const int modulus=30; // example modulus=6,12,18,30

user140242

///     This is a implementation of the bit wheel segmented sieve 
///     with max base wheel choice  30 , 210 , 2310

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <cstdlib>
#include <stdint.h>
#include <time.h> 

user140242

///     This is a implementation of the bit wheel segmented sieve with the basis {2,3,5}.

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <cstdlib>
#include <stdint.h>

const int64_t L1_CACHE_SIZE = 32768;

user140242

///     This is a implementation of the  wheel segmented sieve with the basis {2,3,5}.
///     This algorithm uses (sqrt(n) *8/30) space.

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <cstdlib>
#include <stdint.h>

user140242

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <cstdlib>
#include <stdint.h>

int64_t Euclidean_Diophantine( int64_t coeff_a, int64_t  coeff_b)
{
    // return y in  Diophantine equation  coeff_a x + coeff_b y  = 1

user140242

With the sieve of Eratosthenes algorithm in the Boolean vector SIEVE of size (n+1) initially all set to true
multiples of primes p can be set to false so:

for (p=2; p<=sqrt(n); p++)
    if (SIEVE[p])
        for (m=p*p; m<n+1; m+=p)
           SIEVE[m]=false;


In wheel sieve with base bW   ( bW<sqrt(n)  and  bW  divisible by prime p with p<=p_s ).

user140242

///     This is a implementation of the  wheel segmented sieve with the basis {2,3}.
///     This algorithm uses O(sqrt(n)/3) space.

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <cstdlib>
#include <stdint.h>

user140242

///     This is a implementation of the  wheel segmented sieve for counting primes.

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <cstdlib>
#include <stdint.h> 

void Sieve_Wheel_Base_6(int64_t  dim_step, std::vector<char> &Primes5mod6, std::vector<char> &Primes1mod6)