问题标签 [primes]

我想打印前 10000 个素数。谁能给我最有效的代码？说明：

1. 如果您的代码在 n > 10000 时效率低下，则无关紧要。
2. 代码的大小无关紧要。
3. 您不能以任何方式对值进行硬编码。

好吧，所以也许我不应该把这个问题缩小太多......我已经看过关于找到前 10000 个素数的最有效方法的帖子。我正在寻找所有可能的方法。目标是为素性测试提供一站式服务。任何和所有人们知道的寻找素数的测试都是受欢迎的。

所以：

• 求素数有哪些不同的方法？

我正在通过 projecteuler.net 上的问题来学习如何在 Erlang 中编程，而我最难的是创建一个可以在不到一分钟的时间内创建所有低于 200 万的素数的素数生成器。使用顺序样式，我已经编写了三种类型的生成器，包括 Eratosthenes 的筛子，它们都没有表现得足够好。

我认为并发 Sieve 会很好用，但我收到 bad_arity 消息，我不知道为什么。关于我为什么遇到问题或如何正确编码的任何建议？

这是我的代码，注释掉的部分是我试图使事情并发的地方：

在网上，我发现这段 Ruby 代码适用于 N >= 0，它确定 N 是否为素数。据我所知，它看起来像是在玩正则表达式，但我不知道它是如何工作的。有人可以告诉我它是如何工作的吗？

我一直在尝试通过 Project Euler 进行工作，并且注意到一些问题要求您确定素数作为其中的一部分。

1. 我知道我可以将 x 除以 2, 3, 4, 5, ..., X 的平方根，如果我得到平方根，我可以（安全地）假设这个数字是素数。不幸的是，这个解决方案似乎很笨拙。

2. 我已经研究过更好的算法来确定一个数字是否是素数，但很快就会感到困惑。

有没有一种简单的算法可以确定 X 是否为素数，并且不会让普通程序员感到困惑？

非常感谢！

我正在尝试通过 Project Euler 工作，但在问题 03 上遇到了障碍。我有一个适用于较小数字的算法，但问题 3 使用了一个非常非常大的数字。

问题03： 13195的质因数是5、7、13和29。600851475143这个数的最大质因数是多少？

这是我在 C# 中的解决方案，我认为它已经运行了将近一个小时。我不是在寻找答案，因为我确实想自己解决这个问题。主要是寻求帮助。

这是否被视为有效的素数生成器。在我看来，这非常有效。是使用流使程序运行更慢吗？

我正在尝试将此提交给SPOJ，它告诉我超出了我的时间限制...

编辑：该程序应该在输入中指定的数字之间生成素数。（有关详细信息，请参见此处：Prime Generator Problem）

-托梅克

省略计算素数的方法和分解方法的细节。

为什么要分解？

它的应用有哪些？

我有一系列随机数。范围实际上由用户确定，但最多为 1000 个整数。它们被放置在这个：

并且值是这样插入的：

我正在创建一个单独的函数来查找所有非质数。这就是我现在所拥有的，但我知道这是完全错误的，因为我在这个系列中得到了素数和复合数。

这种方法通常在我只有从 0 到 1000 的一系列数字时有效，但是当我的数字乱序和重复时，它现在似乎不起作用。有没有更好的方法来查找向量中的非素数？我很想创建另一个向量，用 n 个数字填充它，然后以这种方式找到非素数，但这会效率低下吗？

好的，由于范围是 0-1000，我想知道创建 0-n 排序的向量是否更容易，然后使用筛子找到素数，这是否更接近？

我们在这里工作很开心。这一切都始于其中一个人设置了 Hackintosh，我们想知道它是否比我们拥有的（几乎）相同规格的 Windows Box 更快。所以我们决定为它写一个小测试。只是一个简单的素数计算器。它是用 Java 编写的，告诉我们计算前 n 个素数所需的时间。

下面的优化版本 - 现在需要约 6.6 秒

我们几乎失去了整个 Hackintosh 与 PC 的情节，只是在优化它时获得了一些乐趣。没有优化的第一次尝试（上面的代码有几个）运行了大约 52.6 分钟，以找到前 150000 个素数。此优化运行大约 47.2 分钟。

如果您想试一试并发布您的结果，请坚持下去。

我运行它的 PC 的规格是 Pentium D 2.8GHz，2GB RAM，运行 Ubuntu 8.04。

迄今为止，最佳优化一直是电流的平方根，由 Jason Z 首次提到。