问题标签 [sieve]

是否需要删除迭代来检查一个数字是否是素数？

前任。37 是素数，检查 18.5（37 的一半）与 6.08（平方根）会减少很多工作，但两者都遵循相同的原则？

抱歉问，我试图巩固我使用数字的平方根来确定它是否是质数的逻辑，并试图向其他人解释它

问题出现在第 5 行我知道实施[False] * ((n-i*i-1)/(2*i)+1)工作，但我不知道为什么。

我正在编写一种方法来找到 n（Eratosthenes 筛）的素数，是的，这是为了家庭作业。我希望在我编写的方法中提高性能。过去几天我一直在调整它，但无法遵循给出的伪代码并提高性能。

伪代码如下：
创建一个数字队列来处理
用整数 2 到 n 填充队列
创建一个空的结果队列来存储素数
重复以下步骤：
通过从数字队列中删除第一个值来获得下一个素数 p
将 p 放入素数的结果队列
循环遍历数字队列，消除所有可被 p 整除的数字，
而（p 小于 n 的平方根）
所有剩余的值都是素数，因此将它们转移到素数结果队列

这是我目前的方法：

该代码适用于查找素数，我需要的是一个仅包含素数的新数组。打印这个时，它有零，因为它的大小相同。任何帮助表示赞赏。谢谢。

我正在尝试将找到的每个质数输入到“筛子”对象链中。下面的代码实现了我最终想要做的事情，但是每个筛子（素数）类都是手动实现的（检查后续数字是否可以被存储的素数整除，然后它们应该被丢弃，否则它们应该被转发到下一个筛子链），有没有一种方法可以动态地做到这一点，即每次找到一个新的素数时，我都必须创建一个筛子对象。任何帮助深表感谢。

我一直试图在 SPOJ 上解决这个相当简单的问题：http ://www.spoj.com/problems/HS08PAUL/ 。

它需要找出可以以 x^2+y^4（其中 x 和 y 是整数）的形式表示的素数（小于 n）的数量。

我提出了一个蛮力解决方案，该解决方案占用了相当长的时间（n ~= 1000000），导致引擎抛出 TLE（超出时间限制）错误。这是源代码：

有没有一种方法可以使这种方法发挥作用？

PS：请忽略不守规矩的异常处理。

我正在尝试获取 64 位整数（大于 32 位）的除数

我的第一种方法（对于小数）是将数字除以直到结果数为 1，计算匹配素数的数量并使用公式 (1 + P1) (1+ P2) ..*(1 + Pn) = Number除数的

例如：

24 = 2 * 2 * 2 * 3 = 2^ 3 * 3^ 1

==> ( 3 + 1)*( 1 + 1) = 4 * 2 = 8 除数

但是对于大整数，这种方法需要多次迭代。我找到了一种名为Quadratic sieve的方法来使用平方数进行因式分解。现在使用我的脚本，这会容易得多，因为数字要小得多。

我的问题是，我怎样才能实现这个二次筛？

J 将通过 p:n 回答第 n 个素数。

如果我要求第 1 亿个素数，我几乎可以立即得到答案。我无法想象 J 会那么快地筛选那个素数，但也没有在表中查找它，因为该表的大小约为 1GB。

有一些方程给出了质数数量的近似值，但它们只是近似值。

J怎么这么快就找到答案了？

我使用以下代码生成了一个简单的筛子-

但我想消除用于查找素数到 b 的额外时间，为此我制作了 m = (ab)/2 并尝试从 b/2 和 sqrt b/2 而不是零开始主 for 循环，但它没有似乎工作，我怎样才能减少额外的计算？提前致谢。