Skip to content

Instantly share code, notes, and snippets.

@vlofgren
Created November 3, 2013 12:38
Show Gist options
  • Select an option

  • Save vlofgren/7289875 to your computer and use it in GitHub Desktop.

Select an option

Save vlofgren/7289875 to your computer and use it in GitHub Desktop.
Sieve of Eratosthenes
class number_series {
int number, factor;
public:
number_series(int number) :
number(number), factor(0) { }
int get(int n) {
if (factor < n) {
factor = (1+(n/number)) * number;
}
return factor;
}
};
class prime_generator {
std::vector<number_series> series;
int prime;
public:
prime_generator() : prime(2) {
series.push_back(number_series(2));
}
int get() {
for (int i = prime+1;;i++) {
for (int j = 0; j < series.size(); j++) {
if (series[j].get(i) == i)
goto irrelevant;
}
prime = i;
series.push_back(number_series(i));
return i;
irrelevant:; // C++ needs named breaks D:
}
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment