From 0545e74aeab679ff67e95b62f788a79d6a31f222 Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Sun, 14 Feb 2016 00:36:49 +0100 Subject: Adding Jojo's Miller-Rabin code to the document and improving prime sieve. --- math/primeSieve.cpp | 34 ++++++++++++++++++++-------------- 1 file changed, 20 insertions(+), 14 deletions(-) (limited to 'math/primeSieve.cpp') diff --git a/math/primeSieve.cpp b/math/primeSieve.cpp index 183d742..4732d0a 100644 --- a/math/primeSieve.cpp +++ b/math/primeSieve.cpp @@ -1,15 +1,21 @@ -#define N 10000001 -vector primes; -//Finds all prime numbers between 0..N -//Use this method for N < 10000000 to avoid memory access errors -void primeSieve() { - bitset isPrime; isPrime.set(); - isPrime[0] = isPrime[1] = 0; - for(ll i = 2; i < N+1; i+=2) { - if(isPrime[i]) { - for(ll j = i*i; j >= 0 && j < N+1; j+=i) isPrime[j] = 0; - primes.push_back(i); - } - if(i == 2) i--; +// Sieb des Eratosthenes. Laufzeit: O(n * log log n) +#define N 100000001 // Bis 10^8 in unter 64MB Speicher. +bitset isPrime; + +inline bool check(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 !isPrime[x / 2]; +} + +inline int primeSieve(int n) { // Gibt die Anzahl der Primzahlen <= n zurück. + int counter = 1; + for (int i = 3; i <= min(N, n); i += 2) { + if (!isPrime[i / 2]) { + for (int j = 3 * i; j <= min(N, n); j+= 2 * i) isPrime[j / 2] = 1; + counter++; + } } -} \ No newline at end of file + return counter; +} -- cgit v1.2.3