Saturday 10 April 2010

C++ implementation of Euler's Sieve algorithm

vector fillVector(long n) {
long max=20*n;
for (long l = 2; l <= 200000; l++) {
vct.push_back(l);
}
return vct;
}

vector removeElement(vector vct, vector elementsVector) {
vector::iterator p;
for (int i = 0; i < elementsVector.size(); i++) {
p = find(vct.begin(), vct.end(), elementsVector[i]);
if (p < vct.end() || ((p == vct.end()) &&(vct.back() == elementsVector[i]))) {
vct.erase(p);
}
}
return vct;
}

void eulerSieve(long n) {
vector range;
vector prime;

range = fillVector(long n);
while (range.size() > 0) {
long front = range.front();
vector toBeRemoved;
cout<<" Front = "< prime.push_back(front);
for (int i = 0; i < range.size(); i++) {
long temp = front * range[i];
if (temp > range.back()) {
break;

}
toBeRemoved.push_back(temp);

}
range = removeElement(range, toBeRemoved);
range = removeElement(range, vector (1,front));
}
cout << "Prime :" << prime.at(n) << endl;

}