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

有什么方法可以改善该程序的运行时间？我从在线裁判那里获得了超过时间限制的错误，并且看来我的程序运行缓慢？
因此，这是该程序的问题：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;
}

最佳答案

要解决此问题，您需要学习“ Eratosthenes筛”。


首先，从here了解其工作原理。但是，这还不足以解决这个问题。由于该算法的复杂度为O（n.log（log（n）））。因此，如果我们将n =1000000000。它将肯定无法执行。
现在，该优化它了。从here读取。但是，我们还没有完成。
（完成以上两个操作后，请阅读本节）因为我们要找到素数是[m，n]的范围。因此，首先使用Eratosthenes筛子（sqrt（10 ^ 9）= 31622.7，小于32000）创建一个介于2到32000之间的质数列表（我们称其为primeList）。现在，检查[m，n]范围内的每个数字k

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

3.2。如果数字k> 32000，并且不能被

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