projanmo forum find primes

prime.cpp

#include <iostream>
#include <map>
#include <vector>
#include <cstdlib>

using namespace std;

void all_primes(int n, vector<int> &primes) {
    if(n < 2)
        return;

    primes.push_back(2);
    map<long, int> sieve;
    map<long, int>::iterator it;

    long x, p;
    for(long q=3; q<=n; q+=2) {
        it = sieve.find(q);
        if(it == sieve.end()) {
            primes.push_back(q);
            x = q * q;
            if(x <= n)
                sieve[x] = q;
        }
        else {
            p = it->second;
            sieve.erase(it);
            x = p + q;
            if(x <= n) {
                while(sieve.find(x) != sieve.end() or !(x & 1))
                    x += p;
                sieve[x] = p;
            }
        }
    }
}

int main(int argc, char *argv[]) {
    vector<int> primes;
    int n;

    if(argc == 2) {
        n = atoi(argv[1]);
    }
    else {
        cout << "Until which number do you want primes? ";
        cin >> n;
    }

    all_primes(n, primes);

    for(vector<int>::iterator it=primes.begin(); it != primes.end(); it++)
        cout << *it << ", ";
    cout << endl;
    cout << primes.size() << " primes found in [0, " << n << "]" << endl;

    return 0;
}