c++ - 为什么迭代一个 vector 这么慢？

Question

我在做Project Euler #7 ，您可以在其中计算第 10,001 个素数。我编写了一个简单的函数来检查整数是否为质数:

bool isPrime(int p)
{
    if (p % 2 == 0 || p <= 1)
    {
        return false;
    }
    for (int i=3; i<=(int)sqrt((double)p)+1; i+=2)
    {
        if (p % i == 0)
        {
            return false;
        }
    }
    return true;
}

然后在主程序中，我从 2 开始遍历所有后续的奇数，计算每个素数:

int count(1);
int i(1);
while (count != 10001)
{
    i += 2;
    if (isPrime(i))
    {
        count++;
    }
}

std::cout << "Answer: " << i << std::endl;

然后我认为我可以通过跟踪到目前为止找到的所有素数并将它们输入我的 isPrime 函数来改进此函数，如下所示:

bool isPrime(int p, std::vector<int> primes)
{
    if (p <= 1) 
    {
        return false;
    }
    for (std::vector<int>::iterator it=primes.begin(); it!=primes.end(); it++)
    {
        if (p % *it == 0)
        {
            return false;
        }
        else if (*it > (int)sqrt((double)p)+1)
        {
            return true;
        }
    }
    return true;
}

并且主程序改为:

int count(1);
int i(1);
std::vector<int> primes(1,2);
while (count != 10001)
{
    i += 2;
    if (isPrime(i, primes))
    {
        count++;
        primes.push_back(i);
    }
}

std::cout << "Answer: " << primes.back() << std::endl;

我的代码的第一个版本在不到一秒的时间内得到了答案，而第二个版本则需要一分钟多的时间。我不明白为什么会这样，当然第二个版本应该更快，因为 isPrime 正在迭代更小的数字范围？如果有人可以提供任何建议，谢谢。

Answer 1

您应该将 isPrime() 的签名更改为

bool isPrime(int p, const std::vector<int>& primes)

避免每次调用该函数时都复制素数。