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 << " "; }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter