问题标签 [primes]

所以我会称自己为一个相当新手的程序员，因为我在学校里主要专注于硬件，而不是很多计算机科学课程。

于是我解决了 Project Euler 的问题 7：

通过列出前六个素数：2、3、5、7、11 和 13，我们可以看到第 6 个素数是 13。

第10001个质数是多少？

我设法在 Java 中毫无问题地解决了这个问题，但是当我运行我的解决方案时，它需要 8 秒并更改几秒钟才能运行。我想知道如何从编程的角度而不是数学的角度来优化它。

数组循环和 while 语句是消耗处理时间的主要因素吗？以及如何优化？再次不要寻找一个花哨的数学方程..在解决方案线程中有很多。

SPOILER下面列出了我的解决方案。

}

我正在尝试解决Project Euler上的问题 50 。不要给我答案或为我解决它，只是尝试回答这个具体问题。

目标是找到添加到低于一百万的素数的最长的连续素数之和。我写了一个筛子来找到n以下的所有素数，我已经确认它是正确的。接下来，我将使用以下方法检查每个连续素数子集的总和：

我有一个空列表sums。对于每个素数，我将它添加到中的每个元素sums并检查新的总和，然后将素数附加到sums.

这是在python中

我想知道我是否要求check()两个或多个连续素数的总和低于一百万

问题是有一个素数 953，可以写成 21 个连续素数之和，但我没有找到它。

我最近参加了我学校的一个小型 Java 编程竞赛。我和我的搭档刚刚完成了我们的第一个纯 oop 课程，大多数问题都超出了我们的范围，所以我们解决了这个问题（我稍微解释一下）：“给定一个输入整数 n，返回下一个整数和它的反面也是素数，例如如果 n = 18 你的程序应该打印 31" 因为 31 和 13 都是素数。然后，您的 .class 文件将有一个包含 1-2,000,000,000 的所有可能数字的测试用例，并且它必须在 10 秒内返回正确答案才能被视为有效。

我们找到了一个解决方案，但是对于更大的测试用例，它需要超过 10 秒。我相当肯定有一种方法可以将循环范围从 n,..2,000,000,000 向下移动，因为当 n 是一个低数字时需要循环那么远的可能性很小，但是无论哪种方式，当一个数字时我们都打破了循环在这两种情况下都是素数。起初我们从 2,..n 开始循环，不管它有多大，然后我想起了只循环到 n 的平方根的规则。关于如何使我的程序更高效的任何建议？我没有上课处理算法的复杂性分析。这是我们的尝试。

ps 抱歉，如果我的代码格式错误，这是我第一次在这里发帖。此外，输出必须在每行之后有一个“#”，这就是循环之后的行的含义。感谢你们提供的任何帮助！！！

我在RosettaCode上找到了以下 Java 代码示例：

• 我不特别了解 Java，但了解此代码段的所有方面，除了正则表达式本身
• 正如您在内置 PHP 函数中找到的那样，我对 Regex 具有基本到基础的高级知识

如何.?|(..+?)\\1+匹配素数？

我做了一个程序，它返回所有小于 200 万的素数之和。我真的不知道这个是怎么回事，当正确答案是 142913828922 时，我得到 142891895587 作为我的答案。它似乎缺少一些素数。我很确定 getPrime 函数可以正常工作。我之前使用过几次并且工作正常。代码如下：

问题

在这个项目中，您将编写一个 Java 程序，它从标准输入中读取一个正整数 n，然后打印出前 n 个素数。如果存在整数 k 使得 m = kd ，即如果 d 均分到 m，我们说整数 m 可被非零整数 d 整除。等效地，如果 m 的（整数）除以 d 的余数为零，则 m 可被 d 整除。我们也可以通过说 d 是 m 的除数来表达这一点。一个正整数 p 称为素数，如果它的唯一正因数是 1 和 p。该规则的一个例外是数字 1 本身，它被认为是非质数。非素数的正整数称为合数。欧几里得证明了有无穷多个素数。素数序列和复合序列的开头如下：

有很多方法可以测试一个数字的素数，但也许最简单的方法就是简单地进行试除法。以 m 除以 2 开始，如果它被整除，则 m 不是素数。否则，除以 3，然后是 4，然后是 5，依此类推。如果在任何点 m 被发现可以被 2 dm-1 范围内的数字 d 整除，则停止，并得出结论 m 是合数。否则，得出 m 是素数的结论。片刻的思考表明，人们不需要通过数字 d 进行任何尝试除法，数字 d 本身是复合的。例如，如果试除以 2 失败（即余数非零，因此 m 是奇数），则试除以 4、6 或 8 或任何偶数也必须失败。因此，要测试一个数 m 的素数，只需用小于 m 的素数进行试除即可。此外，没有必要一直到 m-1。只需在 2 pm 范围内将 m 除以素数 p 即可。为了看到这一点，假设 m >1 是复合的。那么存在正整数 a 和 b 使得 1 < a < m，1 < b < m，并且 m = ab 。但如果 a > m 和 b > m 都存在，则 ab > m，与 m = ab 相矛盾。因此 a 或 b 之一必须小于或等于 m 。

要在 java 中实现此过程，您将编写一个名为 isPrime() 的函数，其签名如下：

此函数将根据 m 是素数还是合数返回真或假。数组参数 P 将包含足够数量的素数来进行测试。具体来说，在调用 isPrime() 时，数组 P 必须包含（至少）在 2 pm 范围内的所有素数 p。例如，要测试 m = 53 的素数，必须按 2、3、5 和 7 进行连续试除。因为 11 > 53 ，我们不再继续。因此，函数调用 isPrime(53, P) 的前提条件是 P[0] = 2 、 P[1] = 3 、 P[2] = 5 和 P[3] = 7 。在这种情况下，返回值将是 true，因为所有这些划分都失败了。与测试 m =143 类似，必须按 2、3、5、7 和 11 进行试除（因为 13 > 143 ）。因此函数调用 isPrime(143, P) 的前提是 P[0] = 2 、 P[1] = 3 、 P[2] = 5、 P[3] = 7 和 P[4] =11。在这种情况下，返回值将是假的，因为 11 除以 143。函数 isPrime() 应该包含一个循环，该循环遍历数组 P，进行试除法。此循环应在 2 试除法成功时终止，在这种情况下返回 false，或者直到 P 中的下一个素数大于 m 时，在这种情况下返回 true。本项目中的 main() 函数将读取命令行参数 n，分配一个长度为 n 的 int 数组，用素数填充数组，然后根据下面描述的格式将数组的内容打印到 stdout。在函数 main() 的上下文中，我们将此数组称为 Primes[]。因此数组 Primes[] 在这个项目中扮演着双重角色。一方面，它用于收集、存储和打印输出数据。另一方面，它被传递给函数 isPrime() 以测试新整数的素数。每当 isPrime() 返回 true 时，新发现的素数将被放置在数组 Primes[] 中的适当位置。这个过程之所以有效，是因为，如上所述，测试整数 m 所需的素数仅在 m 范围内，并且在测试 m 时，所有这些素数（以及更多）将已经存储在数组 Primes[] 中。当然，有必要手动初始化 Primes[0] = 2，然后使用函数 isPrime() 继续测试 3, 4, ... 的素数。并且在测试 m 时，所有这些素数（以及更多）都将存储在数组 Primes[] 中。当然，有必要手动初始化 Primes[0] = 2，然后使用函数 isPrime() 继续测试 3, 4, ... 的素数。并且在测试 m 时，所有这些素数（以及更多）都将存储在数组 Primes[] 中。当然，有必要手动初始化 Primes[0] = 2，然后使用函数 isPrime() 继续测试 3, 4, ... 的素数。

以下是要在函数 main() 中执行的步骤的概要。

• 检查用户是否提供了一个可以解释为正整数 n 的命令行参数。如果命令行参数不是单个正整数，您的程序将打印如下示例中指定的用法消息，然后退出。
• 分配长度为 n 的数组 Primes[] 并初始化 Primes[0] = 2 。
• 输入一个循环，该循环将发现后续素数并将它们存储为 Primes[1] 、 Primes[2]、 Primes[3] 、 ...、 Primes[n -1] 。这个循环应该包含一个内部循环，它遍历连续的整数并通过调用带有适当参数的函数 isPrime() 来测试它们的素数。
• 将数组 Primes[] 的内容打印到标准输出，将 10 打印到由单个空格分隔的行。换句话说，Primes[0] 到 Primes[9] 将进入第 1 行，Primes[10] 虽然 Primes[19] 将进入第 2 行，依此类推。请注意，如果 n 不是 10 的倍数，则输出的最后一行将包含少于 10 个素数。

您的程序将被称为 Prime.java，它将产生与下面的示例运行相同的输出。（像往常一样，% 表示 unix 提示符。）

如您所见，不适当的命令行参数会生成与许多 unix 命令类似的使用消息。（尝试执行不带参数的 more 命令以查看此类消息。）您的程序将包含一个名为 Usage() 的函数，该函数具有签名

将这条消息打印到 stderr，然后退出。因此，您的程序将总共包含三个函数：main()、isPrime() 和 Usage()。每个前面都应该有一个注释块，给出它的名称、它的操作的简短描述以及任何必要的先决条件（例如 isPrime() 的先决条件）。参见网页上的示例。

尝试的解决方案

我知道函数 BigInteger.probablePrime(int bitLength, Random rnd) 可能输出任何位长度的素数。我想要一个 Java 中的 REAL 素数。是否有任何 FOSS 库可以以可接受的性能做到这一点？提前致谢！

编辑：

我正在查看 1024 和 2048 位素数。

我使用埃拉托色尼筛法和 Python 3.1编写了一个素数生成器。该代码在ideone.com上以 0.32 秒的时间正确而优雅地运行，以生成高达 1,000,000 的素数。

问题是，当我尝试生成高达 1,000,000,000 的数字时，内存不足。

可以想象，分配 10 亿个布尔值（ Python 中每个1 字节4 或 8 字节（见注释））确实不可行，所以我研究了bitstring。我想，为每个标志使用 1 位会更节省内存。然而，该程序的性能急剧下降 - 运行时间为 24 秒，质数高达 1,000,000。这可能是由于位串的内部实现。

您可以注释/取消注释这三行，以查看我更改为使用 BitString 的内容，如上面的代码片段。

我的问题是，有没有办法加快我的程序，有或没有位串？

编辑：请在发布之前自己测试代码。自然，我不能接受运行速度比我现有代码慢的答案。

再次编辑：

我已经在我的机器上编译了一个基准测试列表。

I've been doing a few of the challenges on the Sphere Online Judge (SPOJ), but I can't seem to get the second problem (the prime generator) to run within the time limit. How can the speed of the following code be increased?

我正在尝试编写一个简单的筛子函数来计算 clojure 中的素数。我见过这个关于编写有效筛子函数的问题，但我还没有到那个地步。现在我只是想写一个非常简单（而且很慢）的筛子。这是我想出的：

对于小范围，它可以正常工作，但会导致大范围的堆栈溢出：

我认为通过使用recur这将是一个不消耗堆栈的循环结构？我错过了什么？