I have been trying to create a C++ program to find all the prime numbers under a certain integer, n, using the Sieve of Eratosthenes algorithm, which goes as follows:
Create a vector of integers ranging from 2 to n.
Start with the smallest element of the vector, 2, add it to a new vector of primes, and remove all multiples of 2 from the integers vector.
Repeat this process with the new smallest element of the integers vector (i.e. 3) and repeat until the integers vector is empty. The primes vector then contains all the required primes.
Now, this code works:
#include <iostream>
#include <algorithm>
#include <vector>
void printVector(std::vector<int> v){
for(int i: v)std:: cout << i << " ";
std::cout << std::endl;
}
std::vector<int> primesBelow(int n){
std::vector<int> primes {}, integers {};
for(int i = 2; i <= n; i++) integers.push_back(i); //list elements 2 to n
auto ptr = integers.begin(); //pointer to smallest element
while(ptr != integers.end()){
int p = *ptr;
primes.push_back(p);
integers.erase(std::remove_if(integers.begin(), integers.end(), [=](int x){return x%p==0;}), integers.end());
ptr = integers.begin();
}
return primes;
}
int main() {
auto v = primesBelow(100);
printVector(v);
return 0;
}
However, the following code does not work (the only difference is in the while loop):
#include <iostream>
#include <algorithm>
#include <vector>
void printVector(std::vector<int> v){
for(int i: v)std:: cout << i << " ";
std::cout << std::endl;
}
std::vector<int> primesBelow(int n){
std::vector<int> primes {}, integers {};
for(int i = 2; i <= n; i++) integers.push_back(i); //list elements 2 to n
auto ptr = integers.begin(); //pointer to smallest element
while(ptr != integers.end()){
primes.push_back(*ptr);
integers.erase(std::remove_if(integers.begin(), integers.end(), [=](int x){return x%*ptr==0;}), integers.end());
ptr = integers.begin();
}
return primes;
}
int main() {
auto v = primesBelow(100);
printVector(v);
return 0;
}
Notably, the latter program returns all the prime numbers correctly, but also 4. I've worked out that the latter program adds 2 to the list of primes, then adds 3 and removes the multiples of 3, then adds 4 and removes the multiples of 4, etc. But importantly hasn't removed the multiples of 2.
Why does the latter program have this bug, when I have simply replaced the p in the while loop (which is equal to *ptr) with *ptr? I would have thought that ptr and *ptr do not change in each iteration of the while loop (until the last line of the loop, of course), but apparently they do.
std::remove_if() (potentially) re-orders the elements of the vector. Thus, ptr no longer necessarily points to the same value in further calls of the std::remove_if() predicate. By contrast, the value of p is not affected by std::remove_if().
You can see that they aren't the same with a little bit of ad-hoc debugging:
int p = *ptr;
primes.push_back(*ptr);
integers.erase(std::remove_if(integers.begin(), integers.end(), [=](int x){
if (p != *ptr)
std::cout << "Not the same\n"; // would not show if they had the same value
return x%*ptr==0;
}), integers.end());
P.S. It's not important to the outcome of this program, but the iterator of std::vector is not necessarily a pointer.