diff options
Diffstat (limited to 'math/primeSieve.cpp')
| -rw-r--r-- | math/primeSieve.cpp | 22 |
1 files changed, 10 insertions, 12 deletions
diff --git a/math/primeSieve.cpp b/math/primeSieve.cpp index c17b626..82a4cfd 100644 --- a/math/primeSieve.cpp +++ b/math/primeSieve.cpp @@ -1,22 +1,20 @@ #include <iostream> #include <vector> -vector<int> primeSieve(int n) { +using namespace std; + +typedef unsigned long long ll; + +vector<int> primeSieve(ll n) { vector<int> primes; vector<bool> isPrime(n,true); - for(int i = 2; i < n; i+=2) { - if(i*i <= n) { - if(isPrime[i]) { - primes.push_back(i); - for(int j = 2; i*j < n; j++) { - isPrime[i*j] = false; - } + for(ll i = 2; i < n; i+=2) { + if(isPrime[i]) { + primes.push_back(i); + if(i*i <= n) { + for(ll j = i; i*j < n; j+=2) isPrime[i*j] = false; } } - else { - if(isPrime[i]) - primes.push_back(i); - } if(i == 2) i--; } |