问题标签 [primes]

我正在尝试编写一个程序来找到一个非常大的数的最大素数，并尝试了几种不同成功的方法。到目前为止，我发现的所有这些都慢得令人难以置信。我有一个想法，想知道这是否是一种有效的方法：

这种方法需要输入，并会执行以下操作：

200 -> 100 -> 50 -> 25 -> 5（返回）

90 -> 45 -> 15 -> 5（返回）

它将 currentNum 反复除以最小的可除数（通常是 2 或 3），直到 currentNum 本身是素数（没有小于 currentNum 的平方根的可除素数），并假设这是原始输入的最大素数。

这会一直有效吗？如果没有，谁能给我一个反例？

-

编辑：非常大，我的意思是大约 2^40 或 10^11。

这个问题让我觉得有点奇怪。我很好奇您如何表示数据库中的素数列表。我不知道有一种数据类型能够准确一致地存储大量素数。我担心的是，当素数开始包含 1000 位数字时，从数据库中引用可能有点困难。有没有办法在数据库中表示大量素数？我很确定这个话题之前已经讨论过。

与此相关的问题之一是质数不能分解为因子。如果他们可以，这个问题会容易得多。

我想用方法打印出数组中的所有素数。我可以用一个 int 来做，但不知道如何从数组中返回某些数字。感谢帮助！

谢谢你们俩。似乎解决了：

问题是找到第 1000 个素数。我为此编写了以下python代码。问题是，我得到了第 10、第 20 素数的正确答案，但之后每增加 10 就会使我偏离目标。我在这里无法捕捉到错误:(

如果您想知道，count 被初始化为 1，因为我没有测试 2 作为素数（我从 3 开始）并且candidate递增 2，因为只有奇数可以是素数。我知道还有其他方法可以解决这个问题，例如素数定理，但我想知道这种方法有什么问题。另外，如果您有任何优化想法，请提出建议。

谢谢你

我正在尝试学习 F#，所以我访问了Project Euler，我目前正在研究问题 3。

13195 的质因数是 5、7、13 和 29。

数字 600851475143 的最大质因数是多少？

需要考虑的一些事项：

1. 我的首要任务是学习良好的功能习惯。
2. 我的第二个优先事项是我希望它快速高效。

在下面的代码中，我标记了这个问题所涉及的部分。

更新

根据一些反馈，我将代码重构为快 10 倍。

更新

我要感谢大家的建议。这个最新版本是我收到的所有建议的汇编。

这是我能想到的最好的算法。

可以做得更快吗？

这段代码有一个缺陷：由于numbers是一个无序集合，因此不能保证numbers.pop()会从集合中删除最小的数字。不过，它适用于某些输入数字（至少对我而言）：

那是我的 spoj prime 生成器代码。
尽管它会生成与另一个接受的代码相同的输出..

输出说 12 是一个素数，我们知道那是错误的，所以......
我的代码有什么问题，我该如何解决？

最近我一直在研究一个 C++ 素数生成器，它使用阿特金筛 ( http://en.wikipedia.org/wiki/Sieve_of_atkin ) 来生成它的素数。我的目标是能够生成任何 32 位数字。我将主要用于项目欧拉问题。大多数情况下，这只是一个夏季项目。

该程序使用位板来存储素数：即一系列 1 和 0，例如，第 11 位为 1，第 12 位为 0，第 13 位为 1，等等。为了有效地使用内存，这实际上是和字符数组，每个字符包含 8 位。我使用标志和按位运算符来设置和检索位。该算法的 gyst 很简单：使用一些我不假装理解的方程来定义一个数字是否被认为是“素数”。这将在很大程度上得到正确的答案，但几个非素数将被标记为素数。因此，在遍历列表时，您将刚刚找到的素数的所有倍数设置为“非素数”。这具有方便的优势，即所需的处理器时间越少，素数越大。

我已经完成了 90%，但有一个问题：缺少一些素数。

通过检查位板，我确定在第一遍过程中省略了这些素数，这基本上会为许多方程的每个解切换一个数字（参见维基百科条目）。我一次又一次地检查了这段代码。我什至尝试增加维基百科文章中显示的范围，这效率较低，但我认为可能会遇到一些我以某种方式省略的数字。没有任何效果。这些数字只是评估为非质数。我的大部分测试都针对 128 以下的所有素数。在这个范围内，这些是被省略的素数：

23 和 59。

我毫不怀疑，在更高的范围内，会丢失更多（只是不想计算所有这些）。我不知道为什么这些都不见了，但确实如此。这两个素数有什么特别之处吗？我已经进行了两次和三次检查，发现并修复了错误，但我仍然可能缺少一些愚蠢的东西。

无论如何，这是我的代码：

我尽力清理它并使其可读。我不是专业的程序员，所以请见谅。

这是我得到的输出，当我初始化一个名为 pgen 的 PrimeGen 对象时，使用 pgen.printBoard() 打印其初始位板（请注意，在 next() 迭代之前缺少 23 和 59），然后遍历 next() 和打印所有返回的素数：

我是包java.util.concurrent的新手。我使用多线程和单线程策略创建了以下程序测试数字是否为素数。

对于方法loopMT ，它是使用包java.util.concurrent的类的正确方法吗？还有另一种（更安全，更优雅）的方式来编写这个程序吗？我可以在多线程环境中使用 System.out 吗？

非常感谢您的建议

皮埃尔