Write a program to print prime numbers from 1 to N (where n is an integer).
This problem can also be asked like,
i) How to print prime numbers from 1 to 100.
ii) How to print prime numbers from 1 to 1000 etc.
In this tutorial, we are going to learn how to print prime numbers efficiently using sieve algorithm.
Suppose the value of N is 10, So the prime numbers between 1 to 10 is 2, 3, 5, 7.
Before writing a code, let’s first first understand, what is prime number?
What is 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.
a) First, generate a all numbers from 2 to 20:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
b) 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
c) 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 |
Print Prime Numbers from 1 to N
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.
