Generate Prime Numbers between 1 to N – Sieve of Eratosthenes

Write an efficient program to generate prime numbers between 1 to N (Where N is 10, 100, 1000 etc). This question can also be asked like this, Generate prime numbers between 1 to 100 or 1 to 10 etc.

Suppose the value of N is 10, So the prime numbers between 1 to 10 is 2, 3, 5, 7.  Now let’s learn the most efficient algorithm (Sieve of Eratosthenes) to generate Prime Numbers between 1 to N. Before solving this program, let’s understand what is a prime number.

What is a Prime Number ?

A prime number is a whole number, whose only two factors are 1 and itself.

For example – 2, 3, 5, 7, 11 etc. are prime numbers. 2 is the only even prime number.

There are multiple approaches you can use to generate prime numbers but the most efficient algorithm for generating prime number is Sieve of Eratosthenes.

The time complexity of this algorithm is O(n log logn).

Implement a stack using an array

Check whether a Number is Prime or Not

Sieve of Eratosthenes Algorithm

Suppose, we have to print prime numbers between 1 to 20.

1. First, generate a list of integers from 2 to 20:

2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20

2. The first number in the list is 2; cross out every multiple of 2.

Subscribe Our Tutorials

2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20

So following numbers are cross-out. 4  6  8  10  12  16  18  20

3. Next number is 3 cross out every multiple of 3.

2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20

Continue like this. At the end, numbers which are not cross out are prime numbers.

2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20

So the prime numbers between 1 to 20 is 2, 3, 5, 7, 11, 13, 17, 19.

Generate Prime Numbers between 1 to N

Image taken from Wikipedia

Let’s implement Sieve of Eratosthenes algorithm through code.

PHP Program to Generate Prime Numbers between 1 to N

Let’s implement Sieve of Eratosthenes algorithm in PHP .