如何提高主生成器 (SPOJ) 解决方案的效率

Question

素生成器需要一定范围内的质数。

输入：输入以单行中测试用例的数量 t 开头 (t<=10(。在接下来的每条t行中，有两个数字m和n (1 <= m <= n <= 1000000000， n-m<=100000( 用空格分隔。

输出：对于每个测试用例，打印所有素数 p，使 m <= p <= n，每行一个数字，测试用例用空行分隔。

我的程序使用此解决方案完美运行，但超过了时间限制，并且不接受它作为解决方案。

我已经用scanf和printf替换了cin和cout。我已经用while循环替换了循环，什么都没有。我可以采取哪些其他措施来加快解决方案的速度？

#include<iostream>
int prime(unsigned long int p)
{ 
    int f=1,i=2;
    while(i<=p/2)
    {
        if(p%i==0)
        {   f=0;    
            break;
        }
        ++i;
    }
    if(f==1)
    {   printf("%d n",p);
    }
    return 0;
}
int main()
{
    int t, i=0;
    unsigned long int m,n,j;
    scanf("%d",&t);
    while(i<t)
    {
        scanf("%lu%lu",&m,&n);
        for(j=m;j<=n;++j)
        {
            if(j!=1&&j!=0)
                prime(j);
        }
        printf("n");
        ++i;
    }
    return 0;
}

Answer 1

你的代码效率低下，因为你使用慢速算法来查找素数。将 for 循环更改为 while 循环可能不会加快代码速度，但更改为更好的算法会。

更快的算法：

有一种非常简单的算法叫做埃拉托色尼筛。我们首先制作一个bool数组。将它们全部标记为真。这个数组将让我们跟踪哪些数字是素数，哪些不是素数。我们将划掉那些我们知道不是素数的(通过将它们设置为 false(。

1. 从数组中划掉 0 和 1
2. 从 4 开始，划掉所有 2 的倍数
3. 从 6 开始，划掉所有 3 的倍数
4. 从 10 开始，划掉 5 的所有倍数
5. 从 14 开始，划掉 7 的所有倍数
6. (继续此过程(

例：

// takes a reference to a vector of bools 
// a vector is a resizable array
void cross_out_multiples(std::vector<bool>& primes, int num) {
    for(int i = num * 2; i < primes.size(); i += num) {
        primes[i] = false;
    }
}
std::vector<int> findPrimes(int max) {
    std::vector<bool> primes(max); // create array with max elements
    for(int i = 0; i < max; ++i) {
        primes[i] = true;
    }
    // 0 and 1 aren’t prime, so we mark them false
    primes[0] = false;
    primes[1] = false;
    // here we mark multiples of n false
    for(int n = 2; n < max; n++) {
        // if a number isn’t prime, we can skip it
        if(not primes[n]) {
            continue;
        }
        // if n squared is bigger than max, we already
        // crossed out all multiples of n smaller than max
        // so we don’t have any more work to do
        if(n * n > max) {
             break;
        }
        // now we just cross out multiples of n
        cross_out_multiples(primes, n);
    }
    // now, take the numbers that are prime:
    std::vector<int> listOfPrimes;
    for(int i = 0; i < max; i++) {
        // if a number is prime, add it to the list
        if(primes[i]) {
            listOfPrimes.push_back(i);
        }
    }
    return listOfPrimes;
}I

Answer 2

你的代码是正确的，但(非常(效率低下。在线评判不仅要求正确性，还要求效率。

通过两个简单的措施，您的简单扫描算法可以立即变得更快：

1. 仅测试奇数除数

2. 仅测试最多 sqrt(p) 的除数(对于大p远小于 p/2

(

但最终了解埃拉托色尼的筛子。