primes - 需要关于在自由帕斯卡中筛选埃拉托色尼的帮助

Question

我的老师给了我这个：

n<=10^6;

n 个整数数组：ai..an(ai<=10^9);

找到所有素数。

他说了一些关于 eratosthenes 筛子的事情，我读过它，还有轮分解，但我仍然不知道如何让程序（fpc）在 1 秒内运行。？？据我所知这是不可能的，但仍然想知道你的意见。并且通过车轮分解，一个 2*3 的圆圈会将 25 视为素数，我想问是否有办法找出被错误视为素数的车轮的第一个数字。示例：2*3*5 圆，如何找到第一个被视为质数的合数？请帮忙..对不起英语不好。

Answer 1

一个适当的埃拉托色尼筛法应该在大约一秒钟内找到少于十亿个素数；这是可能的。如果您向我们展示您的代码，我们将很乐意帮助您找出问题所在。

没有被 2,3,5 轮子标记的最小组合是 49：下一个最大的不是轮子成员的素数是 7，并且 7 * 7 = 49。

Answer 2

我现在这样做了，它在几毫秒内找到了高达 1000000 的素数，而没有显示所有这些数字。声明一个包含 n + 1 个布尔值的数组 a（如果它是从零开始的）。在开始的第 0 和第 1 个元素是假的，所有其他的都是真（假不是素数）。该算法如下所示：

i = 2;
while i * i <= n
    if a[i] == true
        j = i * i;
        while j < n
            a[j] = false;
            j = j + i;
    i = i + 1;

在循环中，条件是 i * i <= n，因为您从 i * i 开始搜索（比其他素数之一已经找到的更小的素数），所以 i 的平方根不能大于 n。您删除所有素数乘以 n 的数字。时间复杂度为 O(n log log n)。如果要显示素数，则显示数组中值为真的索引。

如果您想找到例如从 0 到 n 的所有半素数（两个素数的乘积），因式分解很有用。然后，您找到从 0 到 n/2 的所有最小素数除数，并检查每个数字是否具有素数除数，以及数除以其素数除数是否有零除数。如果是这样 - 它是一个半素数。我的程序这样写的计算速度比首先找到所有素数然后将它们相乘并将结果保存在数组中快 8 倍。