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**

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.

1 | 2 3 5 7 11 13 17 19 |

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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | //c code to print prime numbers from 1 to N #include <stdio.h> #include <math.h> int main() { int num, i, prime[10000],k=2; printf("Enter number (less than or equal to 10000) \n"); scanf("%d",&num); /* Generate all numbers between 1 to n, Initially assigned zero value */ for(i = 2; i <= num; i++){ prime[i] = 0; } while(k <= sqrt(num)){ for(i = 2; num >= k*i; i++){ /*Marked multiple of number as 1 Those numbers which marked 1 are not a prime number */ prime[k*i] = 1; } k++; } //Print prime numbers for(i = 2; i <= num; i++) { if(prime[i] == 0) { printf("%d\n",i); } } return 0; } |

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