Efficient algorithm to find out all prime numbers with in a given limit

Efficient algorithm to find out all prime numbers with in a given limit.

In this section I will explain the efficient algorithm to find all the prime numbers with in a given limit.

Before that, below is the glimpse of Prime Numbers And Composite Numbers.

What is a Prime Number?

A Prime number is an positive integer greater than one which is divisible only by itself or 1

Example: 2, 3, 5, 7

On the other hand, the numbers that has at least one divisor other than 1 or itself are called composite numbers.

Example: 4, 6, 8, 9, 10

Problem:

Find out all prime numbers smaller than the given integer.

Input: 10

Output: 2, 3, 5, 7

Solution:

The naive approach to solve the problem is take all numbers lesser than or equal to the given number and check each number if it is a prime or not. Though this is a simple approach, if the given limit is quiet large say 1 million, then doing the prime check for all numbers from 2 to 1000000 will be not be time efficient.

We can solve this problem efficiently by applying the Sieve of Eratosthenes algorithm.

Algorithm:(Let N be the given input limit):

Step 1: Create an array of Boolean with size N+1. This array will represent Primeness of all numbers from 2 to N.

Step 2: Take P=2 as initial value

Step 3: Multiply P with numbers starting from 2, 3, 4 and so on.. and mark the corresponding index in the array as not prime.

Step 4: Increment P by 1 and Continue Step 3 and 4 until P < Square Root(N)

Step 5: In the final array the indexes which are not marked are the prime numbers

Code in Java:

---------------------------------------------------

public class Prime {

  public static void findPrimes(int num) {

      boolean[] allNums = new boolean[num + 1];

      for (int i = 2; i <= Math.sqrt(num); i++)

      {

         if (!allNums[i]) {

             for (int j = 2; num >= i * j; j++) {

                 allNums[i * j] = true;

             }

         }

      }

      for (int i = 2; i < allNums.length; i++) {

         if (!allNums[i]) {

             System.out.print(i + " ");

         }

      }

  }

  public static void main(String[] args) {

      findPrimes(48);

  }

}

---------------------------------------------------

Sample Input: 50

Output: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47