问题标签 [primality-test]
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.
haskell - 在 Haskell 中编写 isPrime 函数
我的问题是：
- 这个功能有什么设计问题？
primes - 为什么我们检查 i <= sqrt(n) 来确定一个数是否是素数？
我知道这个问题之前已经回答过，但我不太明白关于这个问题的解释。
我在 HackerRank 上写了 30 天的代码，其中一个练习是检查一个数字是否为质数。不幸的是，我自己做不到，所以我在多次尝试后检查了给定的解决方案。即使在查看了解决方案之后，我也无法理解其中的一行：
为什么sqrt(n)在for循环中使用？
python - Python 中的 Miller-Rabin Primality Test：为什么我不断得到小数。溢出：[]？
我试图在 python 中进行Miller-Rabin Primality Test 。我根据维基百科上的伪代码编写了如下代码：
但是当我运行代码并输入一个像 5336101 这样的素数时，我得到了以下错误：
所以我决定使用 Decimal 模块，修改了几行代码：
- 添加部分：
- 修改部分：
但后来我得到另一个错误：
我怎样才能解决这个问题？
python - 当我输入一个巨大的数字时，为什么 python 在我的素数测试中跳过我的 while 循环？
我目前正在尝试使用 python 进行简单的素数测试来测试素数。
这是我为测试制作的代码：
我运行代码，它适用于小数字。然后我输入一个巨大的数字（为方便起见，我选择了2^128），它返回 True。但是当我输入 2^129, 2^130, 2^131, 2^132（等等）时，它总是返回 True。我相信我的循环已被跳过。为了验证这一点，我修改了如下代码：
我再次测试了一些小数字，它会打印出正确的 f 值。但是对于任意大的数字（可能高于 '2^50'），它只会打印 3（f 的初始值）。所以我确信这个while循环已经被跳过了。
有没有办法来解决这个问题？
附言：
我还做了其他素数测试。但我想用这个测试来验证这些测试的结果（虽然它需要更长的时间）
我还使用 Numba 来加速我的代码（
@jit(nopython=True)）。这就是我使用很多 np 函数的原因，因为 Numba 使用 NumPy 提高工作效率
编辑1：
- 我已经重新测试了代码，它工作得非常好（即使有大量数字），但速度要慢得多。所以我猜想在处理大量数字时 Numba 有问题
python - 使用 Python 的 Lucas-Lehmer 测试不适用于大量数据
我正在尝试编写一个函数，该函数应该接受梅森数并使用 Lucas-Lehmer 素数测试返回它是否是素数。我正在尝试返回 Lucas-Lehmer 序列中生成的最后一个数字，如果它是质数，它应该是 0
我编写了以下函数来执行上述操作
我的问题是此代码适用于小数，例如127但不适用于大数，2305843009213693951例如524287. 我的 Python Jupyter 笔记本挂断了。关于如何获得一个函数的任何建议，该函数将梅森素数作为输入并使用 Lucas Lehmer 测试返回它是否是素数。我需要让它至少工作2^65-1
python - 为什么我的费马素性检验算法这么慢？
我正在学习数论。现在，我想编写一个执行费马素性检验的程序。
首先，我写了一个模平方算法：
然后，我基于上述算法编写了费马素数检验算法。
当我运行prime_test_fermat.py程序时，它并没有停止。这是由 Fermat 素数或我的代码存在错误引起的。
c++ - 这个素数测试函数的时间复杂度
这个函数的时间复杂度是多少
如果我不得不猜测，那将是
c++ - Miller Rabin素性检验的时间复杂度
下面这个算法的时间复杂度是多少？
最近我对素数测试产生了兴趣，并且想知道米勒拉宾的确定性版本的时间复杂度是多少。https://cp-algorithms.com/直接取的代码
我认为时间复杂度至少O(log(d))是因为 binpower 函数是O(log(e)). 该check_composite函数也运行在O(s). 但我遇到的问题是总时间复杂度。
javascript - JavaScript：使用递归检查数字是否为素数
我对如何解决这个问题有点困惑。我需要所有素数才能返回真。如果不返回 false - 我看到我的逻辑包含 2 并且返回 0 所以它自动返回 false，因为 2 的余数为 0。