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 << " "; }