3

好的，第一件事。是的，这个问题来自编程竞赛。不，我不是想作弊，因为比赛已经结束 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;
}
4

4 回答 4

4

为了减少混淆，请创建一个检查数字是否为素数的函数：

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。

于 2013-10-03T13:48:09.343 回答
2

在不超时的情况下解决这个问题需要两件事：

  • 预先计算素数，和
  • 使用二分查找

您需要少于78,500个素数来进行预计算，因此您不必太花哨。你必须做的唯一一件事就是不要浪费时间检查你的候选除数和非素数：使用你迄今为止找到的素数来发现新的素数。这个页面有这种方法的伪代码。

由于您发现素数的方式，素数表将按升序排列。对于每个测试用例，使用二分搜索搜索素数表。尽管线性搜索也可以工作，但当排序免费时，浪费大量 CPU 周期是没有意义的。此外，C++ 标准库具有在已排序容器中查找项目的便捷功能，因此您的搜索可以在一行中编写。

于 2013-10-03T13:36:48.443 回答
2

你在大数上失败了——例如，不小于 1,000,000 的最小素数是 1,000,003。
测试边缘情况很重要。

并使用诸如 Eratosthenes 筛子之类的东西预先计算素数以加快速度。

于 2013-10-03T13:48:18.360 回答
2

I'm not going to solve it for you, but give you some hints.

  1. Use the Sieve of Eratosthenes, which allows you to build up an array that you can afterwards use to know whether a number is prime in O(1).
  2. Build the Sieve array once before you read any numbers, then you can read numbers and check each of them in constant time. Performing the same calculations for each number is overkill.
于 2013-10-03T13:27:50.323 回答