问题标签 [primes]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
algorithm - 计算 phi(k) 为 1
给定一个大的 N，我需要遍历所有 phi(k) 使得 1 < k < N ：
- 时间复杂度必须是
O(N logN)
- memory-complexity 必须是 sub
O(N)（因为 N 的值将在 10 12左右）
是否可以？如果是这样，怎么做？
给定一个大的 N，我需要遍历所有 phi(k) 使得 1 < k < N ：
- 时间复杂度必须是
O(N logN)
- memory-complexity 必须是 sub
O(N)（因为 N 的值将在 10 12左右）
是否可以？如果是这样，怎么做？
phi(k) 的计算必须使用 k 的素数分解来完成，这是唯一合理的方法。如果您需要对此进行复习，维基百科带有公式。
如果您现在必须计算 1 到大 N 之间的每个数字的所有素数除数，那么您将在看到任何结果之前就死于老年，所以我会反过来，即使用它们构建所有低于 N 的数字可能的素数因子，即所有小于或等于 N 的素数。
因此，您的问题将类似于计算一个数字的所有除数，只是您不知道事先在分解中可以找到某个素数的最大次数是多少。调整最初由 Tim Peters 在 python 列表中编写的迭代器（我在博客上写过的东西......）以包含 totient 函数，python 中产生 k，phi(k) 对的可能实现如下：
如果您在计算低于 N 的所有素数方面需要帮助，我也在博客中讨论过它......请记住，虽然计算低于 10 12的所有素数本身就是一项了不起的壮举......
给定一个大的 N，我需要遍历所有 phi(k) 使得 1 < k < N ：
- 时间复杂度必须是
O(N logN) - memory-complexity 必须是 sub
O(N)（因为 N 的值将在 10 12左右）
是否可以？如果是这样，怎么做？
给定一个大的 N，我需要遍历所有 phi(k) 使得 1 < k < N ：
- 时间复杂度必须是
O(N logN) - memory-complexity 必须是 sub
O(N)（因为 N 的值将在 10 12左右）
是否可以？如果是这样，怎么做？
phi(k) 的计算必须使用 k 的素数分解来完成，这是唯一合理的方法。如果您需要对此进行复习，维基百科带有公式。
如果您现在必须计算 1 到大 N 之间的每个数字的所有素数除数，那么您将在看到任何结果之前就死于老年，所以我会反过来，即使用它们构建所有低于 N 的数字可能的素数因子，即所有小于或等于 N 的素数。
因此，您的问题将类似于计算一个数字的所有除数，只是您不知道事先在分解中可以找到某个素数的最大次数是多少。调整最初由 Tim Peters 在 python 列表中编写的迭代器（我在博客上写过的东西......）以包含 totient 函数，python 中产生 k，phi(k) 对的可能实现如下：
如果您在计算低于 N 的所有素数方面需要帮助，我也在博客中讨论过它......请记住，虽然计算低于 10 12的所有素数本身就是一项了不起的壮举......
math - 素数的有效存储
对于图书馆，我需要将第一个素数存储到限制 L。这个集合必须有 O(1) 查找时间（检查一个数字是否是素数）并且它必须很容易，给定一个数字，找到下一个素数（假设它小于 L）。
鉴于 L 是固定的，生成列表的 Eratostene 筛子就可以了。现在，我使用压缩布尔数组来存储列表，其中仅包含 3 到 L（含）之间奇数的条目。这需要 (L-2)/2 位内存。我希望能够在不使用更多内存的情况下静态增加 L。
是否存在使用较少内存且具有相似属性的数据结构？或者至少有恒定的查找时间？（然后可以枚举奇数，直到我们得到一个素数）
（我写这个的语言是Factor，但这个问题在任何具有内置或易于编程的打包位数组的语言中都是相同的）
math - 有没有办法找到第 n 个素数的近似值？
是否有一个函数可以返回第n个素数的近似值？我认为这类似于近似的反素数计数函数。例如，如果我给这个函数 25 它会返回一个大约 100 的数字，或者如果我给这个函数 1000 它会返回一个大约 8000 的数字。我不在乎返回的数字是否是素数，但我确实想要它要快（因此不会生成前n 个素数来返回第n个。）
我想要这样，这样我就可以使用筛子（Eratosthenes或Atkin ）生成前n 个素数。因此，理想情况下， n th的近似值永远不会低估实际n th 素数的值。
（更新：请参阅我的答案，了解找到第n个素数上限的好方法。）
c# - 最优雅的生成素数的方法
实现此功能的最优雅方法是什么：
此函数生成第一个n素数（编辑： where n>1），因此generatePrimes(5)将返回一个ArrayListwith {2, 3, 5, 7, 11}。（我在 C# 中执行此操作，但我对 Java 实现或任何其他类似的语言（所以不是 Haskell）感到满意）。
我确实知道如何编写这个函数，但是当我昨晚完成时，它并没有像我希望的那样好。这是我想出的：
我不太关心速度，尽管我不希望它明显效率低下。我不介意使用哪种方法（naive 或 sieve 或其他任何方法），但我确实希望它相当简短并且很明显它是如何工作的。
编辑：感谢所有回复的人，尽管很多人没有回答我的实际问题。重申一下，我想要一段漂亮干净的代码来生成素数列表。我已经知道如何以多种不同的方式来完成它，但是我很容易编写不太清晰的代码。在这个线程中，提出了一些不错的选择：
- 我最初拥有的更好的版本（Peter Smit、jmservera 和 Rekreativc）
- Eratosthenes (starblue) 筛子的一个非常干净的实现
- 使用 Java 的
BigInteger和nextProbablePrime非常简单的代码，虽然我无法想象它特别有效 (dfa) - 使用 LINQ 懒惰地生成素数列表 (Maghis)
- 将大量素数放在一个文本文件中，并在必要时读取它们（darin）
编辑 2：我已经在 C# 中实现了这里给出的几个方法，以及这里没有提到的另一种方法。他们都有效地找到了前n 个素数（我有一个不错的方法来找到提供给筛子的极限）。
php - 满足条件时如何在 PHP 中打破 for 循环？
我正在努力编写一些检查可分性的代码（是的，它是为了生成素数），我想知道如果条件满足一次，如何停止 for... 循环。像这样的代码：
$testarray整数 1-100 也是如此，$delete数组将根据$testarray. 但是目前，像 12 这样的数字被$delete多次添加，因为它可以被 2、3、4 和 6 整除。当条件匹配一次时，如何通过向前跳过来节省计算机的时间？
caching - F# 正确使用序列缓存
我正在尝试将 Seq.cache 与我制作的函数一起使用，该函数返回一个不包括数字 1 的素数序列，最多为 N。我无法弄清楚如何将缓存的序列保持在范围内但仍然使用它在我的定义中。
关于如何使用 Seq.cache 来加快速度的任何想法？目前，它一直在范围内下降，并且只会降低性能。
java - 使用 Java 的 BigInteger 可能素数
我想打印两个数字之间的所有素数。这是我的代码：
当它以 1 10 运行时，输出为：
为什么不停在7点？
java - 快速迭代具有 5100 万个素数的数据结构
对于加载 5100 万个素数然后迭代它们的任务，最好的数据结构（在 java 中）是什么？
例如，我需要知道介于 1000000000 和同一个数减去 100000 之间的素数。
algorithm - 学习 F# - 打印素数
昨天我开始在空闲时间看 F#。我想我会从打印出所有质数到 100 的标准问题开始。这就是我想出的……
问题是我觉得我是从 C/C# 的角度来处理这个问题的，并没有接受真正的函数式语言方面。
我想知道其他人能想出什么 - 以及是否有人有任何提示/指针/建议。我觉得目前在网络上很难找到好的 F# 内容，而我接触的最后一个函数式语言是大约 5 年前在大学时的HOPE 。
haskell - Haskell：更快的素数求和
免责声明：我正在研究欧拉问题 9。
我将一些相当大的数字相加，从 1 到 2 000 000 的所有素数。
对这些素数求和需要很长时间。我正在使用内置函数“sum”的haskell。
如：
还有其他更快的选择吗？
--我的主要生成器是我代码中的慢速链接。