0

我正在做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迭代更小的数字范围？如果有人可以提供任何建议，谢谢。

4

1 回答 1

3

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

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

避免primes每次调用函数时复制。

于 2013-05-13T11:31:10.030 回答