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

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.

1 | 2 3 5 7 11 13 17 19 |

Let’s implement Sieve of Eratosthenes algorithm through code.

## C Program to Generate 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 | #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; } |