A small implementation of Eratosthenes' sieve.

eratosthenes.cpp

#include <iostream>
#include <vector>
using namespace std;
int main() {
  int n;
  cin >> n;
  vector<bool> composite(n);
  composite[0] = true; // Technically a zero divisor
  composite[1] = true;
  for (int i = 2; i*i < n; ++i) {
    if (composite[i]) continue;
    for (int j = i*i; j < n; j += i) {
    	composite[j] = true;
    }
  }
  for (int i = 0; i < n; ++i) {
    if (!composite[i]) {
      cout << i << endl;
    }
  }
}