Skip to content

Instantly share code, notes, and snippets.

@k06a
Created February 1, 2015 01:02
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 k06a/7daf00b7c72e3db15adc to your computer and use it in GitHub Desktop.
Save k06a/7daf00b7c72e3db15adc to your computer and use it in GitHub Desktop.
Prime numbers integral by Eratosthenes
int64_t nn = 100000000;
vector<int> ip(nn,1);
size_t pos = 2;
ip[0] = 0;
ip[1] = 0;
while ((pos = find(ip.begin()+pos, ip.end(), 1) - ip.begin()) < nn) {
for (size_t j = pos*pos; j < ip.size(); j+=pos)
ip[j] = 0;
pos += 1 + (pos>2);
}
for (int i = 1; i < nn; i++)
ip[i] += ip[i-1];
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment