Return to Answer

Here's a Delphi implementation (not my weapon of choice but I gotta learn it somehow) that draws 100 random primes up to 1,000,000,000 in less than a millisecond:

function HighestPrimeNotAfter (n: Cardinal): Cardinal; const WINDOW_SIZE = 336; var is_composite: array of Boolean; max_factor, window_start: Cardinal; i, prime, start, stride, j, rest: Cardinal; begin SetLength(is_composite, WINDOW_SIZE); max_factor := Trunc(sqrt(n)); if n > WINDOW_SIZE then window_start := n - WINDOW_SIZE + 1 else window_start := 2; for i := Low(primes_up_to_64K) to High(primes_up_to_64K) do begin prime := primes_up_to_64K[i]; if prime > max_factor then BREAK; start := prime * prime; stride := prime shl (prime and 1); // no double-stepping for p == 2, because of the squaring if start >= window_start then j := start - window_start else begin rest := (window_start - start) mod stride; if rest = 0 then j := 0 else j := stride - rest; end; while j < WINDOW_SIZE do begin is_composite[j] := true; Inc(j, stride); end; end; for j := High(is_composite) downto Low(is_composite) do if not is_composite[j] then begin result := window_start + j; EXIT; end; assert(false); result := 0; // suppress compiler warning end; 

The timing includes 0.2 ms for sieving the primes up to 64K into an array of Cardinal, the code for which is trivial and not shown here.

As always with challenges of this type, the trick lies in doing only the work necessary instead of lots more. That's why the solutions proposed here need a thousand times as much CPU and memory as necessary, despite the brilliant micro-optimisations - a fact that calls to mind The Sieve of Smith (I hope that little gem stays around for a while, as a warning about what happens when you start micro-optimising before you're done with algorithmical and architectural optimisation).

The key here is this: the range from which the random primes are to be drawn is huge but the number of random primes to be drawn is minuscule.

Sieving all numbers up to 2^32 requires on the order of several CPU seconds even when done in C/C++ (2 seconds on a single core for an optimised implementation), and the particulars of CLR and C# compiler slow things down further by about one order of magnitude. However, the challenge doesn't ask for the primality classification of four billion numbers, and it doesn't ask for 203,280,221 primes either. It asks only for a hundred random primes.

Hence a quick, easy and brutally simple solution is to implement a segmented (or rather windowed) sieve. The primes up to 64K - the square root of the upper limit - need to be sieved out in the classic manner and kept around, preferably as an array of integers. But that range is tiny and the list needs to hold only a few thousand primes; generating it should take only a few milliseconds even with the most simple and straightforward (unoptimised) code.

To draw a random prime, draw a random number k between 0 and 2^32-1 and sieve the window [k-335, k]. Then scan the window backwards from k and return the first prime you encounter. The window size is based on the fact that the gaps between primes up to 2^32 are no wider than 336; the value needs to be adjusted for processing ranges beyond 4,302,407,359. See The Gaps Between Primes and First Occurrence Prime Gaps, for example.

In this way, drawing a hundred primes requires only the sieving of 2^16 + 100 * 336 = 99136 numbers instead of 2^32, or about 1/43323th (four orders of magnitude less). The windows are so small compared to the total range that you could even scan them using trial division and still be lots faster than with a full-range sieve.

A Challenge Problem

Given an extremely large int upper limit, perhaps anything over 1 billion, build a random list of 100 primes. You cannot hardcode any known prime counts.

As always with challenges of this type, the trick lies in doing only the work necessary instead of lots more. That's why the solutions proposed here need a thousand times as much CPU and memory as necessary, despite the brilliant micro-optimisations - a fact that calls to mind The Sieve of Smith (I hope that little gem stays around for a while, as a warning about what happens when you start micro-optimising before you're done with algorithmical and architectural optimisation).

The key here is this: the range from which the random primes are to be drawn is huge but the number of random primes to be drawn is minuscule.

Sieving all numbers up to 2^32 requires on the order of several CPU seconds even when done in C/C++ (2 seconds on a single core for an optimised implementation), and the particulars of CLR and C# compiler slow things down further by about one order of magnitude. However, the challenge doesn't ask for the primality classification of four billion numbers, and it doesn't ask for 203,280,221 primes either. It asks only for a hundred random primes.

Hence a quick, easy and brutally simple solution is to implement a segmented (or rather windowed) sieve. The primes up to 64K - the square root of the upper limit - need to be sieved out in the classic manner and kept around, preferably as an array of integers. But that range is tiny and the list needs to hold only a few thousand primes; generating it should take only a few milliseconds even with the most simple and straightforward (unoptimised) code.

To draw a random prime, draw a random number k between 0 and 2^32-1 and sieve the window [k-335, k]. Then scan the window backwards from k and return the first prime you encounter. The window size is based on the fact that the gaps between primes up to 2^32 are no wider than 336; the value needs to be adjusted for processing ranges beyond 4,302,407,359. See The Gaps Between Primes and First Occurrence Prime Gaps, for example.

In this way, drawing a hundred primes requires only the sieving of 2^16 + 100 * 336 = 99136 numbers instead of 2^32, or about 1/43323th (four orders of magnitude less). The windows are so small compared to the total range that you could even scan them using trial division and still be lots faster than with a full-range sieve.

As always with challenges of this type, the trick lies in doing only the work necessary instead of lots more. That's why the solutions proposed here need a thousand times as much CPU and memory as necessary, despite the brilliant micro-optimisations - a fact that calls to mind The Sieve of Smith (I hope that little gem stays around for a while, as a warning about what happens when you start micro-optimising before you're done with algorithmical and architectural optimisation).

The key here is this: the range from which the random primes are to be drawn is huge but the number of random primes to be drawn is minuscule.

Sieving all numbers up to 2^32 requires on the order of several CPU seconds even when done in C/C++ (2 seconds on a single core for an optimised implementation), and the particulars of CLR and C# compiler slow things down further by about one order of magnitude. However, the challenge doesn't ask for the primality classification of four billion numbers, and it doesn't ask for 203,280,221 primes either. It asks only for a hundred random primes.

Hence a quick, easy and brutally simple solution is to implement a segmented (or rather windowed) sieve. The primes up to 64K - the square root of the upper limit - need to be sieved out in the classic manner and kept around, preferably as an array of integers. But that range is tiny and the list needs to hold only a few thousand primes; generating it should take only a few milliseconds even with the most simple and straightforward (unoptimised) code.

To draw a random prime, draw a random number k between 0 and 2^32-1 and sieve the window [k-335, k]. Then scan the window backwards from k and return the first prime you encounter. The window size is based on the fact that the gaps between primes up to 2^32 are no wider than 336; the value needs to be adjusted for processing ranges beyond 2^32. See The Gaps Between Primes and First Occurrence Prime Gaps, for example.

In this way, drawing a hundred primes requires only the sieving of 2^16 + 100 * 336 = 99136 numbers instead of 2^32, or about 1/43323th (four orders of magnitude less).

As always with challenges of this type, the trick lies in doing only the work necessary instead of lots more. That's why the solutions proposed here need a thousand times as much CPU and memory as necessary, despite the brilliant micro-optimisations - a fact that calls to mind The Sieve of Smith (I hope that little gem stays around for a while, as a warning about what happens when you start micro-optimising before you're done with algorithmical and architectural optimisation).

The key here is this: the range from which the random primes are to be drawn is huge but the number of random primes to be drawn is minuscule.

Sieving all numbers up to 2^32 requires on the order of several CPU seconds even when done in C/C++ (2 seconds on a single core for an optimised implementation), and the particulars of CLR and C# compiler slow things down further by about one order of magnitude. However, the challenge doesn't ask for the primality classification of four billion numbers, and it doesn't ask for 203,280,221 primes either. It asks only for a hundred random primes.

Hence a quick, easy and brutally simple solution is to implement a segmented (or rather windowed) sieve. The primes up to 64K - the square root of the upper limit - need to be sieved out in the classic manner and kept around, preferably as an array of integers. But that range is tiny and the list needs to hold only a few thousand primes; generating it should take only a few milliseconds even with the most simple and straightforward (unoptimised) code.

To draw a random prime, draw a random number k between 0 and 2^32-1 and sieve the window [k-335, k]. Then scan the window backwards from k and return the first prime you encounter. The window size is based on the fact that the gaps between primes up to 2^32 are no wider than 336; the value needs to be adjusted for processing ranges beyond 4,302,407,359. See The Gaps Between Primes and First Occurrence Prime Gaps, for example.

In this way, drawing a hundred primes requires only the sieving of 2^16 + 100 * 336 = 99136 numbers instead of 2^32, or about 1/43323th (four orders of magnitude less). The windows are so small compared to the total range that you could even scan them using trial division and still be lots faster than with a full-range sieve.