Primzahlsieb

Signed-off-by: kittobi1992 <Tobias.Heuer@gmx.net>

1 files changed, 24 insertions, 0 deletions

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