只是我正在寻找的一个例子:我可以用一点代表每个奇数对于给定的数字范围(1,10),从3开始:
1110
以下字典可以挤得更对吗?我可以通过一些工作来消除五的倍数,但是以1,3或7或9结尾的数字必须存在于位数组中 . 希望这能澄清我想要的东西 .
我正在寻找最好的算法,检查数字是否为素数,即布尔函数:
bool isprime(number);
我想知道实现此功能的最佳算法 . 当然,我可以查询一个数据结构 . 我 define the best algorithm ,是为范围(1,N)产生具有最低内存消耗的数据结构的算法,其中N是常数 .
23 回答
有很多方法可以做primality test .
您没有真正的数据结构可供查询 . 如果你有很多要测试的数字,你应该运行probabilistic test,因为它们更快,然后用deterministic test跟进它以确保数字是素数 .
你应该知道最快算法背后的数学不适合胆小的人 .
一般素数测试的最快算法是AKS . 维基百科的文章描述了它的长度和原始论文的链接 .
如果你想找到大数字,请查看具有特殊形式的素数,如Mersenne primes .
我通常实现的算法(易于理解和编码)如下(在Python中):
它是经典
O(sqrt(N))
算法的变体 . 它使用这样一个事实:素数(除了2和3)的形式为6k - 1
或6k + 1
,并且只看这种形式的除数 .有时,如果我真的想要速度并且范围有限,我实现了基于Fermat's little theorem的伪素数测试 . 如果我真的想要更快的速度(即完全避免O(sqrt(N))算法),我预先计算误报(参见Carmichael数字)并进行二分搜索 . 这是迄今为止我实施过的最快的测试,唯一的缺点是范围有限 .
在我看来,最好的方法是使用以前的方法 .
互联网上有第一批
N
素数列表,N
至少延伸至fifty million . 下载文件并使用它们,'s likely to be much faster than any other method you' ll想出来 .如果你想要一个实际的算法来制作你自己的素数,维基百科在素数here上有各种好东西,包括各种方法的链接,以及主要测试here,基于概率和快速确定性方法 .
应该齐心协力找到最初的十亿(甚至更多)素数并将它们发布到网上的某个地方,以便人们可以一次又一次地停止做同样的工作...... :-)
https://en.wikipedia.org/wiki/AKS_primality_test
根据维基百科,the Sieve of Eratosthenes有complexity O(n * (log n) * (log log n)) and requires O(n) memory - 所以它测试特别大的数字 .
方太晚了,但希望这会有所帮助 . 如果您正在寻找大素数,这是相关的:
要测试大的奇数,您需要使用Fermat测试和/或Miller-Rabin测试 .
这些测试使用模幂运算,这是非常昂贵的,对于
n
位取幂,你至少需要n
大int乘法和n
大int divison . 这意味着模幂运算的复杂度为O(n³) .所以在使用大枪之前,你需要进行相当多的试验 . 但是不要天真地做,有办法快速做到这一点 . 首先将尽可能多的素数相乘,然后将许多素数组合成用于大整数的词 . 如果使用32位字,则乘以3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 = 3234846615,并使用欧几里德算法计算最大公约数 . 在第一步之后,数字减少到字大小以下并继续算法而不执行完整的大整数除法 . 如果GCD!= 1,这意味着你乘以的素数之一除以数字,所以你有一个证明它不是素数 . 然后继续31 * 37 * 41 * 43 * 47 = 95041567,依此类推 .
一旦你以这种方式测试了几百(或千)个素数,你可以做40轮Miller-Rabin测试以确认数量是素数,经过40轮你可以肯定数量是素数只有2 ^ -80的机会它是不是(你的硬件更可能发生故障......) .
In Python 3:
Explanation: 素数是一个只能被1和1整除的数字 . 例如:2,3,5,7 ......
1) if a<2: 如果"a"小于2则不是素数 .
2) elif a!=2 and a % 2 == 0: 如果"a"可以被2整除,那么它绝对不是素数 . 但是如果a = 2,我们不想评估它,因为它是素数 . 因此条件a!= 2
3) return all (a % i for i in range(3, int(a 0.5)1)):**首先看一下python中all()命令的作用 . 从3开始,我们将"a"除以它的平方根(a ** 0.5) . 如果"a"可被整除,则输出将为False . 为什么平方根?让's say a=16. The square root of 16 = 4. We don' t需要评估到15 . 我们只需要检查到4,说它不是素数 .
Extra: 用于查找范围内所有素数的循环 .
Python 3:
我有一个功能,直到(2 ^ 61)-1这里:
Explanation:
all()
函数可以重新定义为:all()
函数只是通过一系列bools /数字,如果它看到0或False
则返回False
.sqrt()
函数只是执行数字的 square root .例如:
num % x
部分返回num / x的 remainder .最后,
range(2, int(sqrt(num)))
意味着它将创建一个从2开始并在int(sqrt(num)+1)
结束的 list有关范围的更多信息,请查看website!
num > 1
部分只是检查变量num
是否大于1,因为1和0不被视为素数 .我希望这有帮助:)
在Python中:
从数学形式主义到Python的更直接的转换将使用 all(n % p != 0... ) ,但这需要严格评估p的所有值 . 如果找到True值, not any 版本可以提前终止 .
Primes数字javascript的最佳算法
One can use sympy .
来自sympy docs . 第一步是寻找微不足道的因素,如果找到这些因素可以快速返回 . 接下来,如果筛子足够大,则在筛子上使用二分法搜索 . 对于较小的数字,使用已知在其范围内没有反例的碱基进行一组确定性的Miller-Rabin测试 . 最后,如果数量大于2 ^ 64,则执行强大的BPSW测试 . 虽然这是一个可能的主要测试,我们认为存在反例,但没有已知的反例
与已经提到的AKS算法类似的想法
查找某个范围内的数字是否为素数 .
你可以尝试这样的事情 .
以前的大多数答案都是正确的,但这里还有一种方法可以测试数字是素数 . 作为复习, prime numbers 是大于1的整数,其唯一因子是1和它本身 . (source)
Solution:
通常情况下,您可以构建一个循环并开始测试您的号码,看它是否可以被1,2,3整除......直到您正在测试的数字......等但是为了减少检查时间,您可以将您的号码除以数字值的一半,因为数字不能被任何超过其值的一半的任何值整除 . 例如,如果要查看100是素数,则可以循环到50 .
Actual code :
我们可以使用java流在O(sqrt(n))中实现它;考虑到noneMatch是一个shortCircuiting方法,当发现不需要确定结果时停止操作:
在Java-8流和lambdas的帮助下,它可以在几行中实现:
性能应接近O(sqrt(N)) . 也许有人发现它很有用 .
我比较了最受欢迎的建议的效率,以确定一个数字是否为素数 . 我在
ubuntu 17.10
上使用了python 3.6
;我测试的数字高达100.000(您可以使用下面的代码测试更大的数字) .第一个图比较了函数(在我的答案中进一步解释),表明在增加数字时,最后一个函数的增长速度不如第一个函数快 .
在第二个图中,我们可以看到,在素数的情况下,时间稳定增长,但非素数不会在时间上如此快速地增长(因为大多数数字可以在早期被消除) .
以下是我使用的功能:
all()
的构造:for
循环的版本:这是我的脚本来比较变体:
运行函数
compare_functions(n=10**5)
(数字最多为100.000)我得到这个输出:然后,运行函数
compare_functions(n=10**6)
(数字高达1.000.000)我得到这个输出:我使用以下脚本绘制结果:
最小的记忆?这不是最小的,但是朝着正确的方向迈出了一步 .
当然,您必须指定
CheckPrimality
的定义 .我认为最快的一个是我制作的方法 .