Skip to content

Instantly share code, notes, and snippets.

@nsmgr8
Created June 16, 2011 19:16
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save nsmgr8/1030002 to your computer and use it in GitHub Desktop.
Save nsmgr8/1030002 to your computer and use it in GitHub Desktop.
projanmo forum find primes
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment