算法问题，抽空讨论下 [prime is in p].神作出来也有些年了。我不太明白，神作出来前是神马情况。从0到N 挨个搜索判断，也不就是O(n)吗？

　[本文发送自华新手机Wap版] [chancing (3-5 20:08, Long long ago)] [ 传统版 | sForum ][登录后回复]1楼

我记得是polynomial to the number of digits给的是一串0跟1吧，判断这个数是不是prime

我要查一下原paper[icky (3-5 20:23, Long long ago)] [ 传统版 | sForum ][登录后回复]2楼

目测偶数都可以忽略不计啊...for i = 3:2:sqrt(p)
你懂得
end
[功夫熊猫 (3-5 20:42, Long long ago)] [ 传统版 | sForum ][登录后回复]3楼

(引用 功夫熊猫:目测偶数都可以忽略不计啊...for i = 3:2:sqrt(p) 你懂得 end )这么写CS大一就被虐了

SoCer懂的[icky (3-5 22:13, Long long ago)] [ 传统版 | sForum ][登录后回复]4楼

说的是位数从头直接数就exponential了 　[本文发送自华新手机Wap版] [id_rsa (3-6 0:23, Long long ago)] [ 传统版 | sForum ][登录后回复]5楼

依稀记得有三个指标哈哈。。好像之前的弱鸡算法, 有的可以验证梅森，有的只能给个概率什么的 　[本文发送自华新手机Wap版] [id_rsa (3-6 0:25, Long long ago)] [ 传统版 | sForum ][登录后回复]6楼

(引用 icky:这么写CS大一就被虐了 SoCer懂的)为啥呢 不明觉厉 　[本文发送自华新iOS APP] [功夫熊猫 (3-6 8:37, Long long ago)] [ 传统版 | sForum ][登录后回复]7楼

(引用 icky:我记得是polynomial to the number of digits给的是一串0跟1吧，判断这个数是不是prime 我要查一下原paper)这样是说的过去，只不过这样一来，排序呢。

让你排序若干个数。多少个？按位数，n位。

呵呵。 　[本文发送自华新手机Wap版] [chancing (3-6 8:52, Long long ago)] [ 传统版 | sForum ][登录后回复]8楼

O(log(n)^6)人家是这个[typhoonzj (3-6 11:50, Long long ago)] [ 传统版 | sForum ][登录后回复]9楼

(引用 typhoonzj:O(log(n)^6)人家是这个)同意这个，不过这样一来，神作的标题怎么理解？

神作之前，prime is in p.

神作之后，prime is still in p, but better? 　[本文发送自华新手机Wap版] [chancing (3-6 19:33, Long long ago)] [ 传统版 | sForum ][登录后回复]10楼

(引用 chancing:同意这个，不过这样一来，神作的标题怎么理解？ 神作之前，prime is in p. 神作之后，prime is still in p, but better? )原论文第一段解读了根号n方法不够efficient 　[本文发送自华新iOS APP] [typhoonzj (3-6 22:43, Long long ago)] [ 传统版 | sForum ][登录后回复]11楼