3

我一直在尝试创建一个 C++ 程序来使用Eratosthenes 算法的 Sieve来查找某个整数 n 下的所有素数，如下所示：

  1. 创建一个从 2 到 n 的整数向量。

  2. 从向量的最小元素 2 开始，将其添加到新的素数向量中，并从整数向量中删除 2 的所有倍数。

  3. 对整数向量的新的最小元素（即 3）重复此过程并重复此过程，直到整数向量为空。素数向量然后包含所有需要的素数。

现在，此代码有效：

#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;
}

但是，以下代码不起作用（唯一的区别在于while循环）：

#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;
}

值得注意的是，后一个程序正确返回所有素数，但也返回 4。我计算出后一个程序将 2 添加到素数列表中，然后添加 3 并删除 3 的倍数，然后添加 4 并删除倍数4 等。但重要的是没有删除 2 的倍数。

为什么后一个程序有这个错误，当我简单地p将while循环中的（等于*ptr）替换为*ptr？我会这样认为ptr并且在循环*ptr的每次迭代中都不会改变while（当然，直到循环的最后一行），但显然它们会改变。

4

1 回答 1

3

std::remove_if()（可能）重新排序向量的元素。因此，在谓词ptr的进一步调用中不再一定指向相同的值。std::remove_if()相比之下， 的值p不受 的影响std::remove_if()。

您可以通过一些临时调试看到它们并不相同：

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());

PS 这个程序的结果并不重要，但迭代器std::vector不一定是指针。

于 2021-08-21T20:58:36.797 回答