Prime Numbers: Recursive Screen in C++2 min read


In much of the software that resorts to segmentation, the Eratosthene sieve <N is determined by precalculating the prime numbers up to √N.

This prompted me to write the SieveRecur function that borrows this idea to evaluate the sieve recursively:

Unfortunately, the SieveRecur function is only slightly faster than Sieve0 described in my previous articles:

What is already “not so bad”!

One can of course improve it by avoiding to treat the multiples of some small primes (2, 3, 5, ..).

As I pointed out before, segmentation is not strictly speaking an algorithm!
But rather a “simplification” of the management of virtual memory.
The day our computers will have “enough” (real) memory, the “segmentations” will no longer have any reason to be.

In the meantime, these ideas will encourage me to try to “segment” more powerful algorithms than those usually used!



Leave a Comment