I was working on one of the math problems from Project Euler and wrote some useful little snippets of code. Perhaps could be useful to someone else as well. One of them was a simple class to generate prime numbers in a sequence (you often need them in a sequence when trying to find prime factors). Following piece of C++ code generates prime numbers every time the operator() is called.
Prime factorization is a common task in many number theory problems. There is no water tight guarantees for this code but feel free to use modifications of it as you like. I have not checked for the bounds and other cases. Just a naive implementation. Do post a comment if you have suggestions to improve it though :)
class PrimeGenerator {
private:
int current;
bool prime(int n) {
for (int i=2; i<=n/2; i++) {
if (!(n%i)) return false;
}
return true;
}
public:
PrimeGenerator() : current(1) {}
int operator()() {
while (!prime(++current));
return current;
}
};
The way to use it in code is given below.
for (int i=0; i<20; i++) {
cout<<generator()<<", ";
}
I used the class in a function to find prime factors as given below:
vector<int> primeFactors(int n) {
vector<int> result;
PrimeGenerator generator;
int primeFactor;
int remainder = n;
do {
primeFactor = generator();
while (remainder%primeFactor == 0) {
result.push_back(primeFactor);
remainder /= primeFactor;
}
} while (remainder != 1);
return result;
}
