Prime Number Sieves…
Sieving:
Sieving is a simple technique that is used to separate different particles. A sieve with small holes are used for sifting flour. The fine grained particles flow through the hole and the coarse grained particles stay behind.
Sieve Theory
Sieve Theory is a set of general techniques in number theory designed to count or more realistically estimate the size of sifted sets of integers (ref)
One of the main applications of Sieve Theory is prime number sieving and one of the successful approach in prime number sieving which involves approximating a specific sifted set of numbers(i.e prime numbers) by another, simpler set which is typically somewhat larger than the original set, and easier to analyze
Recently I came across this concept of sieving to obtain the prime numbers of finite length. I researched further and found that there are more than one sieving algorithms for filtering out the prime numbers and I tried out those algorithms in java and thought of writing an article to explain them and speed constraints.
Prerequisites:
All the code samples are posted in : https://github.com/lakshmananSubbiah/PrimeNumberFindingSieves
I use Java Language for the coding the algorithms and BitSet(https://effective-java.com/2015/09/unknown-java-features-part-1-bitset/) to store my prime calculations at every level.
Sieve of Eratosthenes:
Sieve of Eratosthenes is a simple and ancient algorithm to find all the prime numbers up to any finite limit.
The algorithm is simple and as follows
step 1:Have a BitSet initialized to the finite length to which prime numbers need to be printed.
step 2:Start on the first number as 2 and let it be p, start from p*p and mark all the multiples of p as not prime i.e these numbers would be p*p, p*(p+1), p*(p+2) and so on.
step 3:Then find the next unmarked number as p and continue step 2. Continue this until p*p reaches the finite limit n. Then stop. The unmarked numbers will give away the prime numbers in the limit
p.s: This algorithm was developed in 276 BC
Sieve of Atkins:
The sieve of Atkins is a modern algorithm for finding all prime numbers up to a specified integer. Compared with the ancient Sieve of Eratosthenes , which marks off multiples of primes, it does some preliminary work and then marks off multiples of squares of primes, that’s why it has a better theoretical asymptotic complexity with Complexity of (N / (log log N))
Instead of iterating over all the numbers the sieve of atkins uses quadratic equations
4(x*x)+y*y,
3(x*x)+y*y
3(x*x)-y*y
to list out all the prime numbers. The algorithm is as follows:
Step 1:Create a BitSet and mark the elements 2,3,5 as prime by default if the finite length is greater than or equal to 5.
Step 2: For each entry number n in the sieve list, with modulo-sixty remainder r:
- If r is 1, 13, 17, 29, 37, 41, 49, or 53, flip the entry for each possible solution to 4x*x + y*y = n.
- If r is 7, 19, 31, or 43, flip the entry for each possible solution to 3x*x + y*y = n.
- If r is 11, 23, 47, or 59, flip the entry for each possible solution to 3x*x — y*y = n when x > y.
- If r is something else, ignore it completely.
Step 3: Start with the lowest number in the sieve list.Take the next number in the sieve list still marked prime.Include the number in the results list.
Sieve of Sundaram:
This is another sieving algorithm and comparatively this algorithm follows a different approach compared to the other two and is the fastest of the three algorithms when tested with Java.
This algorithm follows a deterministic approach and can be explained as below:
step 1: Create a BitSet of size of the given finite length and initialize the BitSet.
step 2: Start from the integer 1 to n, from this list remove all the numbers of the form 2*i*j+i+j where
i,j ∈ N, 1≤i≤j
i+j+2ij ≤ n
The remaining numbers will be doubled and incremented giving the list of prime numbers up to 2n + 2. i.e If you need the prime numbers up to 100 in this step the remaining unmarked numbers can generate all the prime numbers between 3 and 202. We can then sieve out the needed prime numbers alone.
Conclusion:
Out of the three algorithms to print the prime numbers of a finite length the Sieve of Sundaram stood out to be a little fastest than others for the finite length of 1000. But I have seen some optimization to Atkins algorithm that can increase performance to 5 times of current performance of Atkins algorithm because of its quadratic approach.
Overall it was a good learning experience for me, studying about these different types of algorithms. Leave your thoughts on comments.
