需要帮助免费帕斯卡尔eratosthenes筛

-2

n < = 10^6;

n整数数组：ai..an（ai < = 10^9）;

找到所有素数。

他说了一些关于eratosthenes的筛选，我也读了它，也分析了轮子分解，但我仍然无法弄清楚如何让程序（fpc）在1s中运行。因为我知道这是不可能的，但仍想知道你的意见。和轮子分解，一个2 * 3的圆将25视为一个素数，我想问一下，是否有办法找出错误处理的第一个数字作为素数。例如：2 * 3 * 5圈，如何找到第一个合成号码作为最小号码？请帮助..对不起英语不好。

来源

2014-10-08 dang hoang

看看[Wikipedia]（http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes），还有一个筛子的实例。这比车轮更容易。 – joe 2014-10-08 05:26:22

免费Pascal在demo/text/eratos.pp中附带基本筛选示例轮子分解可能是分配的关键。显示您已有的内容可以使评论更容易。 – 2014-10-08 12:20:07

Eratosthenes的一个适当的筛子应该在大约一秒内找到不到10亿的素数;这是可能的。如果您向我们展示您的代码，我们很乐意帮助您找到问题所在。

不是由2,3,5轮标最小的复合材料是49：下一个最大的黄金没有车轮的成员为7，7 * 7 = 49

来源

2014-10-08 12:40:46 user448810

我现在做到了，它会在几毫秒内找到1000000的质数，而不显示所有这些数字。声明一个n + 1布尔数组（如果它是从零开始的）。在开始的第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（小素数比用其他的素数的一个已经找到），这样方我的根不能大于n。您删除所有与质数相乘的数字，直到n。时间复杂度为O（n log log n）。如果要显示素数，则显示索引，其中数组中的值为true。

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

来源

2014-10-10 22:09:10

需要帮助免费帕斯卡尔eratosthenes筛

回答

相关问题