The times I previously posted were from a VirtualBox VM, limited to 4GB of ram,
and in a "noisy" environment. The times here are derived from my host OS
(PCLinuxOS) with full access to the system's 16GB of ram, in a "quiet"
environment, i.e. I closed everything and rebooted, then just opened a terminal
and ran the timing tests.
[jzakiya@localhost nim]$ time ./ssozp5
Enter integer number: 1_000_000_000
segment has 262144 bytes and 262144 residues groups
prime candidates = 266666665; resgroups = 33333334
create nextp[8x3398] array
perform segmented SoZ
last segment = 41046 resgroups; segment slices = 128
total primes = 50847534; last prime = 999999937
real 0m6.928s
user 0m0.393s
sys 0m0.000s
-----------------------------------------------------------
[jzakiya@localhost nim]$ time ./ssozp5
Enter integer number: 10_000_000_000
segment has 262144 bytes and 262144 residues groups
prime candidates = 2666666665; resgroups = 333333334
create nextp[8x9589] array
perform segmented SoZ
last segment = 148310 resgroups; segment slices = 1272
total primes = 455052511; last prime = 9999999967
real 0m5.355s
user 0m4.247s
sys 0m0.000s
-----------------------------------------------------------
[jzakiya@localhost nim]$ time ./ssozp5
Enter integer number: 100_000_000_000
segment has 262144 bytes and 262144 residues groups
prime candidates = 26666666665; resgroups = 3333333334
create nextp[8x27290] array
perform segmented SoZ
last segment = 172374 resgroups; segment slices = 12716
total primes = 4118054813; last prime = 99999999977
real 0m48.434s
user 0m46.852s
sys 0m0.008s
-----------------------------------------------------------
[jzakiya@localhost nim]$ time ./ssozp5
Enter integer number: 1_000_000_000_000
segment has 262144 bytes and 262144 residues groups
prime candidates = 266666666665; resgroups = 33333333334
create nextp[8x78495] array
perform segmented SoZ
last segment = 150870 resgroups; segment slices = 127157
total primes = 37607912018; last prime = 999999999989
real 11m0.884s
user 10m57.985s
sys 0m0.010s
I also wanted to show that the math that forms the foundation of the Sieve of
Zakiya (SoZ) reduces the number of prime candidates to sieve primes from as you
use more "efficient" Strictly Prime (SP) generators. This makes the SoZ
algorithmically possibly the fastest prime sieve.
To illustrate this, below are comparisons of the sequential SoZ between the P5
and P7 prime generators. Because the P7 generator sieves through 8/30 (26.67%)
of all integers, compared to 2/6 (33.33%) for P5, it greatly reduces the number
of prime candidates it needs to sieve through than P5.
These versions just count the primes <= N, and don't numerate them into a list,
to demonstrate the true performance of the prime sieve itself.
Again, these timings were derived on my host OS in a "quiet" environment,
directly after rebooting.
[jzakiya@localhost nim]$ time ./sozp5d
Enter integer number: 1_000_000_000
50847534
real 0m12.074s
user 0m3.738s
sys 0m0.054s
[jzakiya@localhost nim]$ time ./sozp7d
Enter integer number: 1_000_000_000
50847534
real 0m6.938s
user 0m3.055s
sys 0m0.048s
--------------------------------------------
[jzakiya@localhost nim]$ time ./sozp5d
Enter integer number: 10_000_000_000
455052511
real 0m43.221s
user 0m40.365s
sys 0m0.554s
[jzakiya@localhost nim]$ time ./sozp7d
Enter integer number: 10_000_000_000
455052511
real 0m38.520s
user 0m35.655s
sys 0m0.496s
Because the **"classical Sieve of Eratosthenes"** searches through the entire
number space up to some N, it is always inherently slower than the SoZ method.
The ways to increase its performance is to reduce the number space it sieves,
by eliminating the even numbers (a 50% reduction of the number space) and
applying various wheel and other reduction techniques to eliminate more of the
sieved number space.
The SoZ inherently works on a reduced number space that can theoretically be
made as small as desired by the choice of the prime generator used to perform
the sieve.
The SoZ is also an inherently parallelizable algorithm, which can take
advantage of multicore|threaded systems and CUDA|OpenMP implementations, and
others with GPUs (graphic processing units).
