PHP

PHP Program to Print Prime Numbers between 1 to N using Sieve Algorithm2 min read

Write a php program to print prime numbers between 1 to N. In this tutorial, we are going to use Sieve of Eratosthenes algorithm to print prime numbers between 1 to N.

This question can also be asked like this,




* PHP program to print prime numbers between 1 to 100.
* PHP program to print prime numbers between 1 to 1000.

How to Print Prime Numbers using Sieve of Eratosthenes Algorithm

The sieve of Eratosthenes is the most efficient algorithm to print all prime numbers between 1 to n.  Let’s understand this algorithm with example. Let suppose, we have to print prime numbers between 1 to 20.

i). First, generate a list of integers between 2 to 20:

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

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

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

iii)  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.

PHP Program to Print Prime Numbers between 1 to N

We have discussed the algorithm. Let’s write a php code to implement Sieve of Eratosthenes algorithm.

Leave a Comment