Screening tests up to 10 ^ 12

Question

I am working on what requires me to generate all primes up to 10 ^ 12.

Since I never needed this many primes before, I usually just implement the algorithm on this web page here

The problem here, of course, is that 10 ^ 12 is greater than the maximum value for an integer, and as a result, I cannot create an array of this size.

I am not familiar with the methods that could be used to create so many primes, and I wondered if anyone could shed light on the situation.

Answer 1

You will need a segmented sieve.

The basic idea of ​​a segmented sieve is to select screening samples smaller than the square root of n, select a sufficiently large segment size, which nevertheless fits into memory, and then sift each of the segments in turn, starting with the smallest, in the first segment the smallest multiple of each sifting sifting that is inside the segment is calculated, and then the sieving multiplicity of sifting is designated as compound in the usual way; when all sifting primes are used, the remaining unmarked numbers in the segment are primary. Then, for the next segment, for each sifting primer you already know the first plural number in the current segment (it was the multiple that finished the sifting for this stroke in the previous segment), so you sift through each sifting, and so on until you finish .

Consider an example of screening from 100 to 200 in segments 20; There are 5 sifting primes 3, 5, 7, 11, and 13. In the first segment, from 100 to 120, the bitcry has 10 slots, with a slot 0 corresponding to 101, a slot k corresponding to 100 + 2k + 1, and slot 9 corresponding to 119. The smallest a multiple of 3 in a segment is 105, corresponding to slot 2; slots 2 + 3 = 5 and 5 + 3 = 8 are also a multiple of 3. The smallest multiple of 5 is 105 in slot 2, and the slot 2 + 5 = 7 is also a multiple of 5. The smallest multiple of 7 is 105 in slot 2, and slot 2 + 7 = 9 is also a multiple of 7. And so on.

The primes function takes the arguments lo, hi, and delta; lo and hi must be even, with lo <hi and lo must be greater than the square root of hi. The size of the segment is twice as large. Array ps of length m contains sifting primes smaller than the square root of hi, and 2 are removed, since even numbers are ignored, calculated by a normal Eratosthenes sieve. The qs array contains the offset into the bit lattice of the smallest multiple in the current segment of the corresponding sifting. After each segment, lo advances twice, so the number corresponding to the index i of the bitrate is equal to lo + 2 i + 1.

function primes(lo, hi, delta) sieve := makeArray(0..delta-1) ps := tail(primes(sqrt(hi))) m := length(ps) qs := makeArray(0..m-1) for i from 0 to m-1 qs[i] := (-1/2 * (lo + ps[i] + 1)) % ps[i] while lo < hi for i from 0 to delta-1 sieve[i] := True for i from 0 to m-1 for j from qs[i] to delta step ps[i] sieve[j] := False qs[i] := (qs[i] - delta) % ps[i] for i from 0 to delta-1 t := lo + 2*i + 1 if sieve[i] and t < hi output t lo := lo + 2*delta 

For the sample above, this is called a prime number (100, 200, 10). In the above example, qs is originally [2,2,2,10,8,8], corresponding to the smallest multiple of 105, 105, 105, 121 and 117, and is reset for the second segment [1,2, 6,0,11], which corresponds to the smallest multiple of 123, 125, 133, 121 and 143.

Delta value is critical; you must make the delta as large as possible, so long that it fits in the cache for speed. Use your language library for bitarray, so you only take one bit for each sieve location. If you need a simple Eratosthenes sieve to calculate screening tests, this is my favorite:

 function primes(n) sieve := makeArray(2..n, True) for p from 2 to n step 1 if sieve(p) output p for i from p * p to n step p sieve[i] := False 

These functions are in pseudocode; you will have to translate to Java with the corresponding integer data types. If the pseudo-code says exit, you can print a stroke or collect prime numbers in an array, no matter what you do with them.

I did a great job with primes on my blog, including the Prime Numbers Programming essay, which includes a segmented sieve on the last page.

Answer 2

The real solution is to find another way to solve the main problem without generating a complete set of primes. According to the Number Number Theorem, the average gap between primes is ln (1e12), about 27.6. This gives an estimate of more than 39e9 primes less than 1e12.

You probably don't need all of them. Learn how to generate probable primes and / or simple numerical testing. Of course, it is impossible to know exactly what to do without knowing the main problem that you are trying to solve.

Answer 3

Here is my Java code for calculating prime segments:

 /** * Computes the primes in a range using the sieve of Eratosthenes. * The size of the range must not exceed Integer.MAX_VALUE. * * @param start The start index of the prime sieve. * @param limit Primes will be sieved up to but not including this limit. * * @return A bit set representing the integer range from start to limit. * Each bit in this set is set to true if and only if * the corresponding integer is prime. */ public static BitSet computePrimes(long start, long limit) { if (limit - start > Integer.MAX_VALUE) { throw new IllegalArgumentException(); } final long sqrtLimit = sqrtCeil(limit); final BitSet primes = computePrimes((int) sqrtLimit); final BitSet segment = new BitSet(); if (0 - start >= 0) { segment.set((int) (0 - start), false); } if (1 - start >= 0) { segment.set((int) (1 - start), false); } segment.set((int) (Math.max(0, 2 - start)), (int) (limit - start), true); for (int d = 2; d < sqrtLimit; d++) { if (primes.get(d)) { final int remainder = (int) (start % d); final long mStart = start - remainder + (remainder == 0 ? 0 : d); for (long m = Math.max(mStart, d * d); m < limit; m += d) { segment.clear((int) (m - start)); } } } return segment; } 

To calculate prime numbers for sifting segments, a standard sieve is required (it calculates it again for each segment, you must change it):

 /** * Computes the primes using the sieve of Eratosthenes. * * @param limit Primes will be sieved up to but not including this limit. * * @return A bit set where exactly the elements with prime index * are set to true. */ public static BitSet computePrimes(int limit) { final BitSet primes = new BitSet(); primes.set(0, false); primes.set(1, false); primes.set(2, limit, true); for (int d = 2; d < sqrtCeil(limit); d++) { if (primes.get(d)) { for (int m = d * d; m < limit; m += d) { primes.clear(m); } } } return primes; } 

Note that factorizing wheels can speed this up to three times. See Also this answer , the main sieve is the same.