# Sieve of Eratosthenes In C

Hey Learner, Here in this article, we will learn the algorithm of Sieve of Eratosthenes In C. So if you want to learn this algorithm these types of algorithms, then follow our site for easy to learn. So let’s get started.

Sieve of Eratosthenes in C is the algorithm, which is one of the most efficient ways to find all primes smaller than n when n is smaller than 10 million or so in a very fast way and easily with less space and time complexity.

### What is the Complexity of Sieve of Eratosthenes.

To find the prime number between 1 to n in O(N) time by using the Sieve Of Eratosthenes algorithm.

## Sieve of Eratosthenes In C Algorithms for Sieve of Eratosthenes is used for prime number with less time complexity and fast in the compilation.

### Algorithms for Sieve of Eratosthenes

Step 1. Create array integers from 2 to n: (2, 3, 4, …, n).
Step 2. Initially, let p equal 2, the first prime number.
Step 3. Starting a loop from (p=2;p*p <=n;p++ )
Step 4. if ( prime [p] == true)
Step 5. For (i=p*p;i<=n ;i=i+p) prime[p]=false;
Step 6. and repeat from step 3.

## Program For Sieve of Eratosthenes in C (Find Prime Number from 2 to n)

``````#include<stdio.h>
int main()
{
int n;
printf("Enter the Number : ");
scanf("%d",&n);
int i,j,arr[n];

for(i=1; i<=n; i++)
{
arr[i]=1;
}

for(i=2; i*i<=n; i++)
{
if(arr[i]==1)
{
for(j=i*i; j<=n; j+=i)
{
arr[j]=0;
}
}
}
for(i=2; i<n; i++)
{
if(arr[i]==1)
printf("%d\t",i);
}
}``````
```Input : 50

Output : 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47```

## Program For Sieve of Eratosthenes in C ( Find prime Number between two number)

``````#include<stdio.h>
int main()
{
int first, last;
printf("Enter the First number to last Number of Limit to Check : ");
scanf("%d %d",&first, &last);

int i,j, arr[last];

for(i=2; i<=last; i++)
{
arr[i]=1;
}

for(i=2; i*i<=last; i++)
{
if(arr[i]==1)
{
for(j=i*i; j<=last; j+=i)
{
arr[j]=0;
}
}
}

for(i=first; i<=last; i++)
{
if(arr[i]==1)
printf("%d\t",i);
}
}``````
```Input : 10 100

Output : 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97```