1

这里 x,y<=10^12 和 yx<=10^6

我从左到右循环并检查每个数字的素数。当x和y有点像10 ^ 11和10 ^ 12时，这种方法非常慢。有更快的方法吗？我将所有素数存储到 10^6..我可以使用它们来查找像 10^10-10^12 这样的巨大值之间的素数吗？

for(i=x;i<=y;i++)
{
    num=i;
    if(check(num))
    {
        res++;
    }
}

我的检查功能

int check(long long int num)
{
    long long int i;
    if(num<=1)
        return 0;
    if(num==2)
        return 1;
    if(num%2==0)
        return 0;
    long long int sRoot = sqrt(num*1.0);
    for(i=3; i<=sRoot; i+=2)
    {
        if(num%i==0)
            return 0;
    }
    return 1;
}
4

4 回答 4

10

使用 Eratosthenes 的分段筛。

也就是说，使用一个位集来存储 和 之间的数字x，y表示x为偏移量和为 [0,yx) 设置的位。然后筛选（消除倍数）小于或等于平方根的所有素数 y。留在集合中的那些数字是素数。

y最多 10 12你必须用最多 10 6的素数进行筛选，这在正确的实现中将花费不到一秒钟的时间。

于 2013-11-07T07:44:12.440 回答
1

该资源通过多种主要搜索算法来提高复杂性/效率。这是最好的描述，即PG7.8（你必须翻译回C++，应该不会太难）

该算法通过从考虑中消除多个先前识别的素数来有效地选择潜在素数，并最小化必须执行以验证每个潜在素数的素数的测试数量。虽然选择潜在素数的效率允许程序每秒筛选更大范围的数字，但程序运行的时间越长，需要对每个潜在素数执行的测试数量确实会继续增加，（但以与其他算法相比，速度较慢）。总之，这些过程为生成素数带来了更高的效率，使得在 PC 上可以在合理的时间内生成甚至 10 位经过验证的素数。

可以开发进一步的跳跃集来消除潜在素数的选择，这些潜在素数可以被已经识别的每个素数考虑在内。虽然这个过程更复杂，但它可以被概括并变得有点优雅。同时，我们可以继续从测试素数集中消除跳过集合消除倍数的每个素数，从而最大限度地减少必须对每个潜在素数执行的测试次数。

于 2013-11-04T13:20:18.933 回答
0

您可以使用埃拉托色尼筛法算法。此页面有一些指向各种语言的实现的链接：https ://en.wikipedia.org/wiki/Sieve_of_Eratosthenes 。

于 2013-11-04T13:11:08.987 回答
0

这是我对 Erathostenes 筛的实现：

#include <string>
#include <iostream>

using namespace std;

const int k = 110000; //you can change this constant to whatever maximum int you would need to calculate
long int p[k]; //here we would store Sieve of Erathostenes from 2 to k
long int j; 

void init_prime() //in here we set our array
{
    for (int i = 2; i <= k; i++)
    {
        if (p[i] == 0)
        {
            j = i;
            while (j <= k)
            {
                p[j] = i;
                j = j + i;
            }
        }
    }
    /*for (int i = 2; i <= k; i++)
        cout << p[i] << endl;*/ //if you uncomment this you can see the output of initialization...
}

string prime(int first, int last) //this is example of how you can use initialized array
{
    string result = "";
    for (int i = first; i <= last; i++)
    {
        if (p[i] == i)
            result = result + to_str(i) + "";
    }
    return result;
}

int main() //I done this code some time ago for one contest, when first input was number of cases and then actual input came in so nocases means "number of cases"...
{
    int nocases, first, last;
    init_prime(); 
    cin >> nocases;
    for (int i = 1; i <= nocases; i++)
    {
        cin >> first >> last;
        cout << prime(first, last);
    }
    return 0;
}

您也可以使用 Erathostenes 筛来计算阶乘。这实际上是我那天能够创建的筛子的最快解释（它可以在不到一秒的时间内计算出这个范围的筛子）

于 2014-09-09T13:11:58.253 回答