Saturday, December 4, 2021
HomeTop Coding QuestionWrite 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)

LEAVE A REPLY

Please enter your comment!
Please enter your name here

- Advertisment -

Most Popular

Recent Comments