From 5ab8a5088b729a9953b8dff1b2a985dc8fb2098b Mon Sep 17 00:00:00 2001 From: mzuenni Date: Mon, 27 Jun 2022 17:19:28 +0200 Subject: updated tcr --- math/primeSieve.cpp | 31 +++++++++++++------------------ 1 file changed, 13 insertions(+), 18 deletions(-) (limited to 'math/primeSieve.cpp') diff --git a/math/primeSieve.cpp b/math/primeSieve.cpp index 286aa1d..68f7fcb 100644 --- a/math/primeSieve.cpp +++ b/math/primeSieve.cpp @@ -1,22 +1,17 @@ -// Laufzeit: O(n * log log n) -// Kann erweitert werden: Für jede Zahl den kleinsten Primfaktor. -// Dabei vorsicht: Nicht kleinere Faktoren überschreiben. -#define N 100000000 // Bis 10^8 in unter 64MB Speicher. +constexpr ll N = 100000000; bitset isNotPrime; +vector primes = {2}; -inline bool isPrime(int x) { // Diese Methode zum Lookup verwenden. - if (x < 2) return false; - else if (x == 2) return true; - else if (!(x & 1)) return false; - else return !isNotPrime[x / 2]; +bool isPrime(ll x) { + if (x < 2 || x % 2 == 0) return x == 2; + else return !isNotPrime[x / 2]; } -inline int primeSieve() { // Rückgabe: Anzahl der Primzahlen < N. - int counter = 1; // Die 2, die sonst vergessen würde. - for (int i = 3; i < N; i += 2) { - if (!isNotPrime[i / 2]) { - for (int j = i * i; j < N; j+= 2 * i) isNotPrime[j / 2] = 1; - counter++; - }} - return counter; -} +void primeSieve() { + // i * i < N is enough for isPrime + for (ll i = 3; i < N; i += 2) { + if (!isNotPrime[i / 2]) { + primes.push_back(i); + for (ll j = i * i; j < N; j+= 2 * i) { + isNotPrime[j / 2] = 1; +}}}} -- cgit v1.2.3