4

我试图找到第 n 个（n <= 2000000）平方自由 半素数。我有以下代码可以做到这一点。

 int k = 0;
for(int i = 0; i <= 1000; i++)
{
    for(int j = i +1 ; j <= 2500; j++ )
    {
        semiprimes[k++] = (primes[i]*primes[j]);
    }
}
 sort(semiprimes,semiprimes+k);

primes[]是一个素数列表。

我的问题是，我得到不同的值n = 2000000，对 for 循环有不同的限制。有人可以告诉正确计算这些限制的方法吗？

提前致谢..

4

2 回答 2

2

您想计算第 n 个第一个半素数无平方数。“第一”意味着您必须在某个值下生成所有这些。您的方法包括生成大量这些数字，对它们进行排序并提取第 n 个第一个值。

这可能是一个好方法，但您必须生成所有数字。在嵌套循环中有两个不同的限制是错过其中一些限制的好方法（在您的示例中，您没有计算primes[1001]*primes[1002]哪个应该在 中semiprimes）。

为避免此问题，您必须计算正方形中的所有半素数，例如[1,L]*[1,L]，其中 L 是两个循环的极限。

要确定 L，您只需要计数即可。令 N 为 下的半素数无平方数的个数primes[L-1]*primes[L-1]。

N = (L * L - L) / 2

L*L 是成对乘法的总数。L 是正方形的数量。这有两个除以二得到正确的数字（因为primes[i]*primes[j] = primes[j]*primes[i]）。

你想选择 L 使得 n<=N。所以对于 n = 2000000 ：

    int L = 2001, k = 0;
    for(int i = 0; i < L; i++)
    {
        for(int j = i+1 ; j < L; j++ )
        {
            semiprimes[k++] = (primes[i]*primes[j]);
        }
    }
    sort(semiprimes,semiprimes+k);
于 2012-05-24T14:09:58.603 回答
0

我不相信通过计算一个盒子内的所有半素数来工作的方法会在任何合理的时间内工作。假设我们绘制前 200 万个半素数的因子 (p,q)。为了使图形更加对称，让我们为 (p,q) 和 (q,p) 绘制一个点。该图没有形成一个漂亮的矩形区域，而是看起来更像双曲线 y=1/x。这个双曲线延伸得很远，在包含这些的整个矩形上进行迭代将浪费大量的计算。

您可能要考虑首先解决“N 以下有多少个半素数？”的问题。然后使用二进制搜索。每个查询都可以在大约 sqrt(N) 步骤中完成（提示：二分搜索再次触发）。您将需要一个相当大的素数表，肯定至少多达 100 万个，甚至可能更多。虽然这可以通过一些预先计算的任意大的常数因子来减少。

于 2012-06-14T04:59:28.847 回答