From 0fb5b77d3faf56b8c1d83516256f359086f3addd Mon Sep 17 00:00:00 2001
From: kittobi1992 <Tobias.Heuer@gmx.net>
Date: Fri, 21 Nov 2014 16:02:51 +0100
Subject: Primzahlsieb

Signed-off-by: kittobi1992 <Tobias.Heuer@gmx.net>
---
 math/primeSieve.cpp | 24 ++++++++++++++++++++++++
 1 file changed, 24 insertions(+)
 create mode 100644 math/primeSieve.cpp

(limited to 'math/primeSieve.cpp')

diff --git a/math/primeSieve.cpp b/math/primeSieve.cpp
new file mode 100644
index 0000000..9981981
--- /dev/null
+++ b/math/primeSieve.cpp
@@ -0,0 +1,24 @@
+#include <iostream>
+#include <vector>
+
+vector<int> primeSieve(int 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 = 1; i*j < n; j++) {
+					isPrime[i*j] = false;
+				}
+			}
+		}
+		else {
+			if(isPrime[i])
+				primes.push_back(i);
+		}
+		if(i == 2)
+			i--;
+	}
+	return primes;
+} 
\ No newline at end of file
-- 
cgit v1.2.3


From f0ca9a96291d0cc2d1af337ca4d6838339f94539 Mon Sep 17 00:00:00 2001
From: kittobi1992 <kittobi1992@users.noreply.github.com>
Date: Fri, 21 Nov 2014 16:07:24 +0100
Subject: Update primeSieve.cpp

---
 math/primeSieve.cpp | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

(limited to 'math/primeSieve.cpp')

diff --git a/math/primeSieve.cpp b/math/primeSieve.cpp
index 9981981..c17b626 100644
--- a/math/primeSieve.cpp
+++ b/math/primeSieve.cpp
@@ -8,7 +8,7 @@ vector<int> primeSieve(int n) {
 		if(i*i <= n) {
 			if(isPrime[i]) {
 				primes.push_back(i);
-				for(int j = 1; i*j < n; j++) {
+				for(int j = 2; i*j < n; j++) {
 					isPrime[i*j] = false;
 				}
 			}
@@ -21,4 +21,4 @@ vector<int> primeSieve(int n) {
 			i--;
 	}
 	return primes;
-} 
\ No newline at end of file
+} 
-- 
cgit v1.2.3


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(-)

(limited to 'math/primeSieve.cpp')

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


From 79901fdf49fd97df29cefa56b26afd9d2e109b81 Mon Sep 17 00:00:00 2001
From: kittobi1992 <kittobi1992@users.noreply.github.com>
Date: Sat, 22 Nov 2014 11:16:18 +0100
Subject: Update primeSieve.cpp

Final update!
---
 math/primeSieve.cpp | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

(limited to 'math/primeSieve.cpp')

diff --git a/math/primeSieve.cpp b/math/primeSieve.cpp
index 82a4cfd..4c82bbe 100644
--- a/math/primeSieve.cpp
+++ b/math/primeSieve.cpp
@@ -7,7 +7,7 @@ typedef unsigned long long ll;
 
 vector<int> primeSieve(ll n) {
 	vector<int> primes;
-	vector<bool> isPrime(n,true);
+	vector<int> isPrime(n,true);
 	for(ll i = 2; i < n; i+=2) {
 		if(isPrime[i]) {
 			primes.push_back(i);
-- 
cgit v1.2.3