算法问题,抽空讨论下 [prime is in p].

2019-07-18 09:06
神作出来也有些年了。我不太明白,神作出来前是神马情况。从0到N 挨个搜索判断,也不就是O(n)吗?

5 个回答

查看全部回答

2019-07-18 09:06

梅馥

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

我要查一下原paper

2019-07-18 09:06

江悦

目测偶数都可以忽略不计啊...
for i = 3:2:sqrt(p)
你懂得
end

2019-07-18 09:06

梅馥

这么写
CS大一就被虐了

SoCer懂的

2019-07-18 09:06

宁艺庆

说的是位数
从头直接数就exponential了

2019-07-18 09:06

宁艺庆

依稀记得有三个指标哈哈。。
好像之前的弱鸡算法, 有的可以验证梅森,有的只能给个概率什么的