From e9fcd01ba01b8ad5db5c72d678a0682bd15334e5 Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Mon, 10 Jul 2017 16:44:39 +0200 Subject: Adding code to count the number of inversions. --- math/primeSieve.cpp | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) (limited to 'math/primeSieve.cpp') diff --git a/math/primeSieve.cpp b/math/primeSieve.cpp index 7e8b288..286aa1d 100644 --- a/math/primeSieve.cpp +++ b/math/primeSieve.cpp @@ -1,4 +1,6 @@ // 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. bitset isNotPrime; @@ -13,7 +15,7 @@ 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 = 3 * i; j < N; j+= 2 * i) isNotPrime[j / 2] = 1; + for (int j = i * i; j < N; j+= 2 * i) isNotPrime[j / 2] = 1; counter++; }} return counter; -- cgit v1.2.3