performance - 更快的素数生成 C#

Question

我知道已经就同一主题提出了很多问题，但这个问题可能有所不同。我研究了一些计算从 2 到 N 的素数的算法。我编写了以下算法来计算一定范围内的素数，例如从 N 到 M，其中 M 可以是大至 10^10，N 和 M 之间的差异可为 10^6。

for (k = 0; k < t; k++)
{
    int[] indexOfPrimes = new int[m[k] - n[k] + 1];

    int index_1=2;
    int index_2=0;
    int counter = 0;

    for (index_1 = 2; index_1 < Math.Sqrt(m[k]);  index_1++)
    {
        counter = 0;
        for (index_2 = index_1*index_1; index_2 <= m[k];)
        {
            if (index_2 >= n[k] && index_2 <= m[k])
                indexOfPrimes[index_2 % (m[k] - n[k] + 1)] = 1;
            index_2 = (index_1 * index_1) + (index_1 * ++counter);
        }
    }

    for (i = n[k]; i <= m[k]; i++)
    {
        if (i == 1)
            continue;
        if (indexOfPrimes[i % (m[k] - n[k] + 1)] != 1)
            Console.WriteLine(i);
    }
    Console.WriteLine("\n");
}

这里带有变量k的循环用于处理t测试用例。当 m[k]>10^7 时，该算法需要大量时间来处理最大范围(即 100000)。

有没有办法不从2开始计算，而是直接从指定范围内开始计算？

有什么方法可以使速度更快吗？

编辑:有人可以给我提供一个足够大的随机输入来测试我的算法吗？它总是给出超过时间限制，但是，它在我的笔记本电脑上只运行了 2.5 秒。

编辑:我在最大输入时将其减少到 1.5 秒。给我错误的答案。不明白为什么。

Answer 1

从算法的角度来看，你想做的是

• 使用任何方法查找 2 到 316 之间的素数
• 使用这些素数筛选 100000 以内的所有数字，从而找到 100000 以内的素数
• 使用 100K 个素数来筛选给定范围，从而找到给定范围内的素数

为了用一个例子来说明最后一点，假设我们知道从 2 到 4 的所有素数，并且我们想要找到 11 到 15 之间的所有素数。第一步是找到 2 之间的素数集合和 4，即 {2,3}。现在我们使用该集合来筛选集合{11,12,13,14,15}。

为此，我们注意到 6*2 是所需范围内 2 的最小倍数，然后我们消除所有 2 的倍数，直到达到范围的末尾，从而消除 12 和 14。

然后我们用 3 重复这个过程，再次消除 12 和 15。该范围内的剩余数字是 11 和 13，所以这些是 11 到 15 范围内的素数。

一个挑战是找到给定素数 p 的最小倍数，且该素数在 N 到 M 范围内>。您可以通过将范围的低端除以 p 并在必要时向上舍入来实现此目的。例如，以下代码查找最小乘数 x，使得 p*x >= N。

int p, N, x;

x = N / p;         // integer division truncates, so x may be too small
if ( p * x < N )   // if p divides N, then p * x == N, 
   x++;            // otherwise we need to adjust x

Example 1: (N = 11, p = 2) ==> (x = 5, but 5*2<11, so x = 6)
Example 2: (N = 12, p = 3) ==> (x = 4, and 3*4==12, so x stays at 4)