Monday, June 21, 2021
Home coding Write a program to find prime number using seive eratoshenes.

# Write a program to find prime number using seive eratoshenes.

Given a number we have to find prime number between that ranges using seive method and print the resultant value .

So what is prime number ?

prime number is a number which has only two factor one is 1 and second is number itself.

Example:

``````input:30
output:2 3 5 7 11 13 17 19 23 29
``````

Logic:

``````Seive algorithm is most optimal algorithm to find a prime number between ranges.
according to this algo
we will create a boolen array to check number is prime or not.``````

Code-

```#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
bool seive[n+1];
memset(seive, true, sizeof(seive));
for (int i=2; i*i<=n; i++)
{
if (seive[i] == true)
{
for (int j=i*2; j<=n; j += i)
{
seive[j] = false;
}
}
}

for (int k=2;k<=n;k++)
{
if (seive[k]==true)
{
cout<<k<< " ";
}
}
}
```

Output:

```30

2 3 5 7 11 13 17 19 23 29 ```

Time complexity:0(N)

Space Complexity:O(N)