From fa83b8c841073b462840260b54593767e597f543 Mon Sep 17 00:00:00 2001
From: kittobi1992 <kittobi1992@users.noreply.github.com>
Date: Fri, 21 Nov 2014 19:33:12 +0100
Subject: Update primeSieve.cpp

fastest prime sieve
---
 math/primeSieve.cpp | 22 ++++++++++------------
 1 file 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--;
 	}
-- 
cgit v1.2.3