sieve of eratosthenes Algorithm
The Sieve of Eratosthenes is an ancient Greek algorithm that efficiently finds all prime numbers up to a specified integer. It was created by the ancient Greek mathematician Eratosthenes in the 3rd century BC and is still one of the most popular algorithms for generating prime numbers today. The algorithm works by iteratively marking the multiples of each prime number, starting from the smallest prime, which is 2, and continuing until all numbers up to the given limit have been checked.
The algorithm begins by creating a list of numbers from 2 to the desired limit (n). It then starts with the first number (which is 2) in the list and marks it as prime. Next, it removes all the multiples of 2 (excluding 2 itself) from the list, as they are not prime. The algorithm then moves to the next unmarked number in the list (which is 3) and marks it as prime, removing all its multiples from the list. This process is repeated for all the remaining unmarked numbers in the list until no more numbers are left to check. At the end of the algorithm, all the marked numbers in the list are prime numbers, and all the multiples of the prime numbers have been removed.
// this is a program to implement sieve algorithm to generate prime numbers.
//https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define endl '\n'
#define pii pair<ll int,ll int>
#define vi vector<ll int>
#define all(a) (a).begin(),(a).end()
#define F first
#define S second
#define hell 1000000007
#define lbnd lower_bound
#define ubnd upper_bound
#define bs binary_search
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
int prime[1000000]={0};
void sieve(int n)
{
for(int i=2;i<=n;i++)
{
if(prime[i]==0)
{
for(int j=2*i;j<=n;j+=i)
prime[j]=1;
}
}
}
int main()
{
ios
int x;
cin>>x;
sieve(x);
//now whichever i>1 has prime[i]==0 , is a prime.
for(int i=2;i<=x;i++)
{
if(prime[i]==0)
cout<<i<<" ";
}
}
