c - spoj.com prime 生成器时间超出限制

Question

提交答案超出了时间限制。我也面临着同样的问题，我在 spoj.com 上提交了另外 2-3 个问题。

http://www.spoj.com/problems/PRIME1/

Peter wants to generate some prime numbers for his cryptosystem. Help him! Your task is to generate all prime numbers between two given numbers!

Input

The input begins with the number t of test cases in a single line (t<=10). In each of the next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space.

Output

For every test case print all prime numbers p such that m <= p <= n, one number per line, test cases separated by an empty line.

Example

Input:

2
1 10
3 5

Output:

2
3
5
7

3
5

Warning: large Input/Output data, be careful with certain languages (though most should be OK if the algorithm is well designed)

这是我的 C 代码。

#include <stdio.h>

int main()
{
    int t,i,k,count;
    long long int j=0,m=0,n=0;

    scanf("%d",&t);

    for(i=1;i<=t;i++)
    {
        scanf("%lld%lld",&m,&n);

        for(j=m;j<=n;j++)
        {
            count=0;
            for(k=1;k<=j/2;k++)
            {
                if(j%k==0)
                    count++;
                if(count>1)
                    break;
            }

            if(count==1)
                printf("%lld\n",j);
        }
        printf("\n");
    }

    return 0;
}

Answer 1

你的算法是 O((m-n)*n)，当然不会在分配的时间限制内运行。让我们检查一下您的代码:

count=0;
for(k=1;k<=j/2;k++)
{
if(j%k==0)
count++;
if(count>1)
break;
}
if(count==1)
printf("%lld\n",j);

微观优化:为什么需要计数器？你可能会得到一个 bool 值。

优化:为什么要测试素数j/2？如果 j 的除数大于 1，则保证 j 的除数最多为 sqrt(j)。

微观优化:根本不考虑偶数，除了 2。

bool prime = j==2 || j%2==1 ;
for(k=2;prime && k*k<=j;k++)
{
if(j%k==0) prime = false;
}
}
if(prime) printf("%lld\n",j);

现在这是 O((m-n)*sqrt(n))，速度快得多。

我想这不会成为限制。您可以轻松扩展第二个微优化以跳过可被 3 整除的数字。

优化:如果这还不够，那么您必须进行伪素性测试。一个很容易在 O(log(n)) 中实现的测试是 https://en.wikipedia.org/wiki/Fermat_primality_test 。这样，复杂度就降到了 O((m-n)*log(n))，应该在可用的时间限制内运行。