c++ - 超过时间限制如何提高速度

Question

有什么办法可以提高这个程序的运行时间吗？我从在线判断中得到时间限制超过错误，并且看起来我的程序运行缓慢？所以，这是这个程序的问题:http://www.spoj.com/problems/PRIME1/

我的代码(c语言):

#include <stdio.h>

void FindPrime (int m, int n)
{
    int i, prime = 1;

    if (m <= n)
    {
        for (i = m - 1; i > 1; i--)
        {
            if (m % i == 0)
            {
                prime = 0;
                break;
            }
        }
        if (prime == 1 && m != 1)
            printf ("%d\n", m);
        FindPrime (m + 1, n);
    }
}

int main ()
{
    int num1, num2, i, cases;

    scanf ("%d", &cases);
    while (cases != 0)
    {
        scanf ("%d %d", &num1, &num2);
        FindPrime (num1, num2);
        printf ("\n");
        cases--;
    }

    return 0;
}

Answer 1

要解决这个问题，您需要学习“埃拉托斯特尼筛法”。

1. 首先，从 here 了解它的工作原理。但是，这还不足以解决这个问题。因为，算法的复杂度是 O(n.log(log(n)))。因此，如果我们输入n = 1000000000。肯定会执行失败。

2. 现在是时候优化它了。从 here 读取。但是，我们已经完成了。

3. (完成上述两部分后请阅读本节)由于我们要找到的素数范围是[m,n] 。因此，首先使用埃拉托斯特尼筛 (sqrt(10^9) = 31622.7) 创建一个 2 到 32000 范围内的素数列表(我们称之为 primeList)，小于 32000)。现在，检查 [m,n]

   范围内的每个数字 k

   3.1。如果数字k在2-32000范围内，并且该数字在primeList中。打印出来。

   3.2。如果数字k> 32000，并且不能被<= sqrt(k)并且也在中的所有数字整除素数列表。打印出来。否则，忽略或不打印它。 (请注意'1'不是质数)。

你可以查看我的solution 。但是，尽管应用的概念相同，但它的实现与我解释的略有不同。