This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/// 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> |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/// 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> |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/// 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; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/// 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> |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 ). |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/// 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> |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/// 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) |
NewerOlder