// Programm: eratosthenes.C
// Primzahlenberechnung - Sieb des Eratosthenes.
#include
#include
typedef std::vector Vec;
int main()
{
std::cout << "Berechne Primzahlen bis: ";
unsigned int n;
std::cin >> n;
std::cout << "Primzahlen in [0," << n << "): ";
Vec is_prime (n, true);
for (unsigned int i = 2; i < n; ++i)
// Invariante: Fuer alle j in [2,n):
// (1) j Primzahl => is_prime[j]
// (2) j % k == 0 fuer ein k in [2,i) => !is_prime[j]
if (is_prime[i]) {
std::cout << i << " ";
// markiere alle echten Vielfachen von i als nicht-prim
for (unsigned int m = 2*i; m < n; m += i)
is_prime[m] = false;
}
std::cout << std::endl;
return 0;
}
