※ 引述《dharma (达)》之铭言： : 前面大家的回应有点难懂 : 要慢慢研究 : 现在先换个简单的问法 : A. : 判别一个数是否为质数 这是P问题　(你的文章标题下错了) 十年前才发现的，论文名称是PRIMES is in P，是重大突破 该演算法後来被大家称做AKS质数检测法 就是前面板友回文提到的 : B. : 不知81785036517是否为质数 : 但要确定277877是否为81785036517因数 : 可以直接拿去除 除法是P问题 长除法的时间复杂度是O(n^2) http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations 请参考division那一栏 : 照直觉说 : 一个大数a，要确认它是不是质数 : 应该远比确认b是不是a的因数难很多 你说的很对 : 那麽 : A应该比B困难啊 你说的很对 : 我哪里误解了 : thanks 你可以这样想： P问题的范围非常非常大， 大到可以同时包含这两个困难度不一样的问题。 至於P究竟有多大，是不是跟NP一样大？ 这是当今的数学难题，还没有人知道怎麽证明。 --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 111.250.72.194 ※ 文章网址: http://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1401664867.A.DCE.html ※ 编辑: DJWS (111.250.72.194), 06/02/2014 07:42:17