Update primeSieve.cpp

fastest prime sieve

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