Re: [问题] 验证某数是否为质数是NP问题 dharma PTT批踢踢实业坊

Re: [问题] 验证某数是否为质数是NP问题

楼主: dharma (é”) 2014-06-01 18:01:09

前面大家的回应有点难懂
要慢慢研究
现在先换个简单的问法
A.
判别一个数是否为质数
B.
不知81785036517是否为质数
但要确定277877是否为81785036517因子
可以直接拿去除
照直觉说
一个大数a，要确认它是不是质数
应该远比确认b是不是a的因子难很多
那么
A应该比B困难啊
我哪里误解了
thanks

作者: Fenikso (薪水小偷) 2014-06-01 19:11:00

"难不够多" 就这样 XD

作者: freef1y3 ( ) 2014-06-01 20:52:00

乘法也比加法难，但两个都是P

作者: stimim (qqaa) 2014-06-01 21:26:00

我觉得你可能看错 B 命题了，可以给来源吗？

继续阅读

Re: [问题] 验证某数是否为质数是NP问题johnathan717 [问题] 验证某数是否为质数是NP问题dharma [问题] 如何以数学公式及算法表达程式tree581 [解题]排列组合CFengY Re: [问题] n^2-1 -puzzle的问题cutekid [问题] 方形转圆形huadi73 [问题] n^2-1 -puzzle的问题soheadsome Re: [问题] ICPC 5713 疑似MST的问题DJWS [问题] ICPC 5713 疑似MST的问题iamnotgm Re: [讨论] Google面试问题johnathan717