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