※ 引述《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一样大？
这是当今的数学难题，还没有人知道怎么证明。