C Program to Print Prime Numbers from 1 to N – Sieve of Eratosthenes

Write a c program to print prime numbers from 1 to N (where n is an integer). This question can also be asked like, print prime numbers from 1 to 100 in c. In this tutorial, we are going to use sieve algorithm to print prime numbers from 1 to N.

Suppose the value of N is 10, So the prime numbers between 1 to 10 is 2, 3, 5, 7.

Now, Let’s learn how to print prime numbers from to 1 to N using Sieve of Eratosthenes. 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 print 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).

C Program to 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.

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

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

Subscribe Our Tutorials

Get Latest Updates on Facebook

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

C Program to Print Prime Numbers from 1 to N

Image taken from Wikipedia

Let’s implement Sieve of Eratosthenes algorithm through code.

C Program to Print Prime Numbers from 1 to N

In this tutorial, we have discussed how we can print prime numbers from 1 to N using sieve algorithm. Let’s write a c program to print prime numbers between  1 to N.

In this video tutorial, I have explained how to print prime numbers using sieve algorithm.

About WebRewrite

I am technology lover who loves to keep updated with latest technology. My interest field is Web Development.
Tagged , , , . Bookmark the permalink.