求两个大数x和y之间素数数的最快方法

Question

这里x，y<=10^12和y-x<=10^6

我从左到右循环，检查每个数字，因为当x和y有点像10^11时，prime..this方法非常慢，而10^12..any更快一些吗？我将所有素数存储到10^6..can，然后使用它们在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;
}

Answer 1

这一资源通过大量的素数搜索算法来提高复杂度/效率。下面是最好的描述，即PG7.8 (您必须将其转换回C++，应该不会太难)

该算法通过从考虑因素中消除已识别素数的倍数，有效地选择潜在素数，并最小化了验证每个潜在素数优先性所必须执行的测试次数。虽然选择潜在素数的效率允许程序每秒钟筛选出更大范围的数字，但程序运行的时间越长，需要对每个潜在素数执行的测试数量就会继续增加(但与其他算法相比，上升速度更慢)。这些过程共同带来了产生素数的更高效率，使得在一台PC上能够在合理的时间内生成甚至10位数验证的素数。 进一步的跳过集可以被开发，以消除潜在素数的选择，这些素数可以被已经识别的每一个素数所考虑。尽管这个过程更复杂，但它可以被概括，并使之变得更优雅。同时，我们可以继续从测试素数集中消除每个跳过集消除倍数的素数，使对每个潜在素数必须执行的测试次数最小化。

Answer 2

您可以使用Eratosthenes算法的筛子。这个页面有一些用不同语言实现的链接：埃拉托斯提尼。

Answer 3

下面是我对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的筛子来计算阶乘。这实际上是我那天所能创建的筛子的最快解释(它可以在不到一秒钟的时间内计算出这个范围的筛子)。