算法问题，抽空讨论下 [prime is in p].
chancing • • 32332 次浏览神作出来也有些年了。我不太明白，神作出来前是神马情况。从0到N 挨个搜索判断，也不就是O(n)吗？
10 条回复
-
#1
我记得是polynomial to the number of digits给的是一串0跟1吧，判断这个数是不是prime
我要查一下原paper -
#2
目测偶数都可以忽略不计啊...for i = 3:2:sqrt(p)
你懂得
end -
#3
这么写CS大一就被虐了
SoCer懂的 -
#4
说的是位数从头直接数就exponential了
-
#5
依稀记得有三个指标哈哈。。好像之前的弱鸡算法, 有的可以验证梅森，有的只能给个概率什么的
-
#6
为啥呢 不明觉厉
-
chancing 楼主#7
这样是说的过去，只不过这样一来，排序呢。
让你排序若干个数。多少个？按位数，n位。
呵呵。 -
#8
O(log(n)^6)人家是这个
-
chancing 楼主#9
同意这个，不过这样一来，神作的标题怎么理解？
神作之前，prime is in p.
神作之后，prime is still in p, but better? -
#10
原论文第一段解读了根号n方法不够efficient