gebaut

1 files changed, 22 insertions, 0 deletions

diff --git a/math/primeSieve.cpp b/math/primeSieve.cpp
new file mode 100644
index 0000000..4c82bbe
--- /dev/null
+++ b/math/primeSieve.cpp
@@ -0,0 +1,22 @@
+#include <iostream>
+#include <vector>
+
+using namespace std;
+
+typedef unsigned long long ll;
+
+vector<int> primeSieve(ll n) {
+	vector<int> primes;
+	vector<int> isPrime(n,true);
+	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;
+			}
+		}
+		if(i == 2)
+			i--;
+	}
+	return primes;
+}