Pages

Showing posts with label Number theory. Show all posts
Showing posts with label Number theory. Show all posts

Thursday, November 23, 2017

Sieve of Eratosthenes In Java

The sieve of Eratosthenes is a famous ancient algorithm to find all prime numbers up to a given limit. We are going to implement this algorithm in Java.


Steps we will follow:

a) Lets we have an array of size 25.
b) First start with 2, remove all numbers which are divisible by 2.
c) Find the next number, which is 3. Remove all numbers which are divisible by 3.
d) Next survivor is 5 and we repeat the same procedure.
e) For the given limit 25, we don't need to find anymore survivor after 5, as 5 X 5 = 25. In other words, we only process up to the square root of the limit.
 f) All survivor numbers in the array are Prime. We save those numbers in a separate array.