I am back Again!!
Today, its all about an interesting Algorithm - "Sieve of Eratosthenes Algorithm".
May be few of us might have come across this. But I found this quite interesting and thought sharing this with you all.
You would get a GIF version of it by searching with the algorithm name in google search. And that GIF version will help you in avoiding the paper work. (CHEAT CODE !!) :)
In our childhood it was quite tough to find out Prime Numbers in a range of number. And it still stands the same if we have to do it without using any mathematical technique. In the attachment there are 2 files- One is Worksheet and the other is Result sheet. The Result in the second sheet has been indicated using the color coding method.
I hope you would be true to do it atleast once without cheating. And please do it and you would find it very easy to get the prime numbers between any range of numbers.
The Algorithm:
1. Write a list of numbers from 2 to the largest number you want to test for primality. Call this List A. (This is the list of squares on the left side of the picture.)
2. Write the number 2, the first prime number, in another list for primes found. Call this List B. (This is the list on the right side of the picture.)
3. Strike off 2 and all multiples of 2 from List A.
4. The first remaining number in the list is a prime number. Write this number into List B.
5. Strike off this number and all multiples of this number from List A. The crossing-off of multiples can be started at the square of the number, as lower multiples have already been crossed out in previous steps.
6. Repeat steps 4 and 5 until no more numbers are left in List A.
Note that, once you reach a number greater than the square root of the highest number in List A, all the numbers remaining in List A are prime.
For Those who would be carried away to write a program on this algorithm -
The complexity of the algorithm is O((nlogn)(loglogn)) and has a memory requirement of O(n).
Please Do write your comments for this attempt !!
Regards,
Anupam
