c++ - 在不超过时间限制的情况下找到素数

Question

好的，首先是第一件事。是的，这个问题来自编程竞赛。不，我不是想作弊，因为比赛已在 4 小时前结束。我很确定我的代码是正确的，但比赛的编译器说它给出了错误的答案。我尝试了其他编译​​器，它说“超出时间限制”。

那么，首先，你能告诉我代码是否正确吗？ [一位编译器说不是]

如果是，那么我怎样才能让它更有效率？ [另一个编译器说它超过了时间限制]

---

PROBLEM A number is called a prime number if it is greater than 1 and has no divisors other than 1 and itself. The first few prime numbers are 2, 3, 5, 7, 11, 13,.. and so on. Given an integer X, find the smallest prime number which is not less than X

Input: The first line contains the number of test cases T. T cases follow. Each test case consists of an integer X in a separate line.

Output: Output T lines, one for each case containing the smallest prime number which is not less than X

Constraints: 1 <= T <= 10 1 <= X <= 1,000,000

Sample Input: 4 8 47 90 1130

Sample Output: 11 47 97 1151

这是我的解决方案:

int main() 
{
    int n;
    long int x, i, a;
    bool isPrime; // This flag will test if number is prime or not?
    cin>>n; // Here "n" will represent the number of test cases
    while(n)
    {
        cin>>x; // "x" is the number to be tested for the nth case

        if(x<=2)
        {
            cout<<2<<endl; // All numbers smaller than 3 will have the smallest prime number as 2.
            continue;
        }
        for(i=x;i<=1000000;i++) // Should I have checked values of "i" for odd numbers only? I forgot to try that... Would it have helped in reducing time complexity?
        {
            isPrime=true;
            for(a=2; a<i; a++) // Okay I tried making it (i/2)+1 but then the compiler said that it was a wrong answer. I am skeptical though...
            {
                if(i%a==0 and i!=2)
                    isPrime=false;
            }
            if(isPrime==true)
            {
                cout<<i<<endl;
                break;
            }
        }

        n--;
    }
    return 0;
}

Answer 1

为了减少混淆，制作一个检查数字是否为素数的函数:

bool IsPrime(int x)
{
    isPrime=true;
    for(int a = 2; a < x; a++)
    {
        if (x % a == 0 && a != 2)
            return false;
    }
    return true;
}

在这里，我没有更改您的代码，只是对其进行了重组。这很好，因为这个功能很小，对它的任何改进都很容易。

移除边缘案例

不需要检查 a == 2，因为你永远不会为 2 调用这个函数。这使得内部循环更小，提供更好的性能。

bool IsPrime(int x)
{
    isPrime=true;
    for(int a = 2; a < x; a++)
    {
        if (x % a == 0)
            return false;
    }
    return true;
}

检查更少的除数

这是一个众所周知的事实，而且很容易检查，检查除数到 sqrt(x) 就足够了。这提供了更好的性能!

bool IsPrime(int x)
{
    isPrime=true;
    for(int a = 2; a * a <= x; a++)
    {
        if (x % a == 0)
            return false;
    }
    return true;
}

此时您的程序可能会被时间检查器接受。如果您仍然想要更好的性能，您可以进一步限制除数。

只检查素数

嗯，不是真正的素数，但最好将检查至少限制为奇数。

bool IsPrime(int x)
{
    isPrime=true;
    static const int a_few_primes[] = {2, 3, 5, 7, 11, 13};
    for (int a: a_few_primes)
    {
        if (x % a == 0)
            return false;
    }
    for(int a = 17; a * a <= x; a += 2)
    {
        if (x % a == 0)
            return false;
    }
    return true;
}

关于 Eratosthenes 筛法的注释，其他一些回答者推荐:它很好，但考虑到测试用例的数量非常少 (10)，您可能并不真的需要它。

编辑:删除了一些有缺陷的性能分析。

筛法需要至少 1000000 次迭代才能构建素数列表。

trial 方法要求每个数少于 500 次迭代，尝试少于 114直到找到一个素数，它会重复 10 次，所以迭代次数小于 500*114*10=570000。