在不超过时间限制的情况下查找素数

Question

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

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

如果是，那么我怎样才能提高时间效率？[另一个编译器说超出了时间限制]

---

问题 如果一个数大于 1 并且除了 1 和它本身之外没有其他约数，则该数称为素数。前几个素数是 2, 3, 5, 7, 11, 13,.. 等等。给定一个整数X，找到不小于X的最小素数

输入：第一行包含测试用例 T 的数量。随后是 T 用例。每个测试用例由一个单独行中的整数 X 组成。

输出：输出T行，每行包含不小于X的最小质数

约束： 1 <= T <= 10 1 <= X <= 1,000,000

输入示例：4 8 47 90 1130

示例输出：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;
}

关于埃拉托斯特尼筛的注释，其他一些回答者推荐：它很好，但考虑到测试用例的数量非常小（10），也许你并不真正需要它。

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

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

Trial 方法需要每个数字少于 500 次迭代，尝试少于114 个数字直到找到素数，并且执行了 10 次，因此迭代次数少于 500*114*10=570000。