// Programm: eratosthenes-it.C
// Primzahlenberechnung - Sieb des Eratosthenes.
#include
#include
typedef std::vector Vec;
typedef Vec::iterator It;
typedef Vec::difference_type Diff;
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 (It i = is_prime.begin() + 2; i != is_prime.end(); ++i)
// Invariante: Fuer alle j in [2,n):
// (1) j Primzahl => *(is_prime.begin() + j)
// (2) j % k == 0 fuer ein k in [2,i-is_prime.begin())
// => !*(is_prime.begin() + j)
if (*i) {
Diff j = i - is_prime.begin();
std::cout << j << " ";
// markiere alle echten Vielfachen von j als nicht-prim
for (It m = i + j; m < is_prime.end(); m += j)
*m = false;
}
std::cout << std::endl;
return 0;
}
