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 that | |
/// uses two vectors in order to have the wheel with the basis {2,3}. | |
/// This sieve 1/3 of the memory is used compared to the traditional sieve. | |
/// For large numbers a double segmentation is used. | |
#include <iostream> | |
#include <cmath> | |
#include <algorithm> | |
#include <vector> | |
#include <cstdlib> |
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) |
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
import math | |
import numpy as np | |
def goldbach(n): | |
# for n>17 goldbach function returns vector G with G[i]=g(2i) for 2<=i<=n/2 | |
Primes5mod6 =np.ones((n//6+1), dtype=bool) | |
Primes1mod6 =np.ones((n//6+1), dtype=bool) | |
imax=math.isqrt(n)//6+1 | |
for i in range(1,imax+1): | |
if Primes5mod6[i]: | |
Primes5mod6[6*i*i::6*i-1]=[False] |
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
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,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
/// 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
// 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 | |
/// 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> |
OlderNewer