问题标签 [primes]

几年前，证明PRIMES 在P 中。是否有任何算法在 Python 中实现其素性测试？我想用一个简单的生成器运行一些基准测试，并亲眼看看它有多快。我会自己实现它，但我对这篇论文的理解还不够。

作为圣诞礼物，我用 Java 编写了一个小程序来计算素数。我的意图是让它通宵达旦，计算下一个素数并将其写入 .txt 文件。早上我会终止程序并将 .txt 文件带给我的朋友过圣诞节。

有什么我应该担心的吗？请记住，这是您正在与之交谈的真正的初学者 Ziggy，而不是一些聪明的错误检查 ASM 家伙。

编辑更具体地说，因为我将在整个晚上计算素数时离开这个程序，我是否有可能遇到某种与内存相关的错误？像，堆压成堆或狗和猫睡在一起？

编辑更具体地说，当文件大小为 4GB 时，我可以输入一行代码来停止打印行吗？只是为了安全？

编辑：成功：整夜离开后，我得到的素数不超过 13 KB，我得到的最高值是 22947217，这就像数万个素数。成功！

作为一个非密码学家，我总有一件让我印象深刻的事情：为什么使用素数如此重要？是什么让它们在密码学中如此特别？

有没有人有一个简单的简短解释？（我知道有很多入门书，应用密码学是圣经，但正如所说：我不打算实现自己的密码算法，而我发现的东西让我的大脑爆炸了——没有 10 页的数学公式请 ：））

感谢所有的答案。我接受了那个让我最清楚实际概念的那个。

哪个是使用 C++ 找出素数的最快算法？我已经使用了筛子的算法，但我仍然希望它更快！

我目前正在尝试一些问题，只是为了练习我的编程技能。（还没有在学校或任何东西上学习，自学）我遇到了这个问题，需要我从给定的 txt 文件中读取一个数字。这个数字是 N。现在我想找到 N <= 10 000 的第 N 个素数。找到它之后，我想把它打印到另一个 txt 文件中。现在对于问题的大部分部分，我能够理解并设计一种获得 N 的方法。问题是我正在使用一个数组来保存以前找到的素数，以便使用它们来检查未来的数字。即使我的数组大小为 100，只要输入整数大约 < 15，程序就会崩溃。

我完全根据我的傻瓜指南和我自己做到了这一点，所以请原谅我算法的一些代码效率低下和一般新手。对于最多 15 个，它也能正确显示素数。

谁能告诉我应该如何改进当前的代码？我正在考虑使用 txt 文件代替数组。那可能吗？任何帮助表示赞赏。

有人可以告诉我这段代码我做错了什么吗？无论如何，它只是打印“计数”。我只想要一个非常简单的素数生成器（没什么花哨的）。

我一直在努力解决 Project Euler 的第27题，但这似乎难倒我。首先，代码运行时间太长（在我的机器上可能需要几分钟，但更重要的是，它返回了错误的答案，尽管在浏览了一段时间后我真的无法发现算法有什么问题.

这是我当前的解决方案代码。

关于如何a）让这个算法真正返回正确答案的任何提示（我认为我至少采取了一种可行的方法）和b）提高性能，因为它显然超过了项目中规定的“一分钟规则”欧拉常见问题。我是函数式编程的新手，所以任何关于我如何考虑更实用的解决方案的问题的建议也将不胜感激。

和 17 一样，是质数，反过来，71 也是质数。

我们设法得到了这个代码，但我们无法完成它。

我的问题是如何添加所有的f s ..

答案应该是 429。

我怎样才能添加所有的f？

注意：下面的版本 2 使用 Eratosthenes 筛。有几个答案对我最初提出的问题有所帮助。我选择了埃拉托色尼筛法，实施了它，并适当地改变了问题的标题和标签。感谢所有帮助过的人！

介绍

我写了这个花哨的小方法，它生成一个包含小于指定上限的素数的 int 数组。它工作得很好，但我有一个担心。

方法

我的顾虑

我担心的是我创建的数组对于该方法将返回的最终元素数量来说太大了。问题是我不知道正确猜测小于指定数字的素数数量的好方法。

重点

这就是程序使用数组的方式。这是我想要改进的地方。

1. 我创建了一个足够大的临时数组，可以容纳每个小于限制的数字。
2. 我生成质数，同时计算我生成了多少。
3. 我制作了一个新的数组，它的维数正确，可以只保存素数。
4. 我将每个素数从巨大的数组复制到正确维度的数组中。
5. 我返回仅包含我生成的素数的正确维度的数组。

问题

1. temp[]我可以将具有非零元素的整个块（一次）复制 到primes[] 而不必遍历两个数组并一个一个地复制元素吗？
2. 是否有任何数据结构的行为类似于可以随着元素的添加而增长的基元数组，而不是在实例化时需要维度？与使用基元数组相比，性能损失是多少？

版本 2（感谢Jon Skeet）：

版本 3（感谢Paul Tomblin）使用Erastosthenes 筛法：

我正在编写一个带有一些素数相关方法的小库。由于我已经完成了基础工作（又名工作方法），现在我正在寻找一些优化。当然，互联网是这样做的好地方。然而，我偶然发现了一个舍入问题，我想知道如何解决这个问题。

在循环中，我用来测试一个数字的素数，搜索直到 sqrt(n) 而不是 n/2 甚至 n - 1 更有效。但是由于舍入问题，一些数字被跳过，因此一些素数被跳过！例如，第 10000 个素数应为：104729，但“优化”版本最终为：103811。

一些代码（我知道它可以进行更多优化，但我一次只能处理一件事）：

I know the squared part fails me (or I fail), tried Math.Ceiling as well, with about the same results.