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

神作出来也有些年了。我不太明白，神作出来前是神马情况。从0到N 挨个搜索判断，也不就是O(n)吗？

请先 登录 后评论
默认排序 时间排序

5 个回答

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

我要查一下原paper
请先 登录 后评论
江悦
目测偶数都可以忽略不计啊...
for i = 3:2:sqrt(p)
你懂得
end
请先 登录 后评论
梅馥
这么写
CS大一就被虐了

SoCer懂的
请先 登录 后评论
宁艺庆
说的是位数
从头直接数就exponential了
请先 登录 后评论
宁艺庆
依稀记得有三个指标哈哈。。
好像之前的弱鸡算法, 有的可以验证梅森，有的只能给个概率什么的
请先 登录 后评论
  • 0 关注
  • 0 收藏，427 浏览
  • 武豪 提出于 2019-07-18 09:06

相似问题