Sieve of Eratosthenes
Fri Jan 21 2022 12:14:59 GMT+0000 (Coordinated Universal Time)
Saved by
@vaibhav_55
vector<bool> primes(100001, true);//global array
// Time complexity :- n(log(log((n)^1/2)))+O(n)
void sieve()
{
int n = 10000;
primes[0] = primes[1] = false; // 0 and 1 are not prime so primes is false;
for (int i = 2; i <= n; i++)
{
if (primes[i] == true)
{
for (int j = i * i; j <= n; j += i)
{
primes[j] = false;
}
}
}
// primes array which has value true are primes
for (int i = 1; i <= n; i++)
if (primes[i])
cout << i << " ";
}
content_copyCOPY
Comments