Sieve of Eratosthenes (Algorithm of generating primes)

[AvDav]

Еще одна задача из той же категории и её компактная реализация:

#include <vector>
#include <iostream>

using namespace std;

void generate_primes(int n) {
	vector<bool> v(n+1, true);
	v[0] = v[1] = false;
	for(int i = 2; i*i <= n; ++i)
		if(v[i]) for(int j = (i << 1); j <= n; j+=i) v[j] = false;
	for(int i = 0; i <= n; ++i)
		if(v[i]) cout << i << endl;
}

int main() {
	generate_primes(100);
	return 0;
}