百科问答小站 logo
百科问答小站 font logo



如何判断一个超级大的数是不是素数? 第1页

  

user avatar   assptiger 网友的相关建议: 
      

现在知乎已经沦落到贴一堆latex就可以骗赞了吗?看来下次我写个数学公式自动生成器就能有赞了?

贴latex就算了,好歹只是不懂强答,那几个民科又是怎么回事?

质量还不如维基百科呢……


素数判定是一个P问题,而且已经有了好几种实用的判定算法。

你说的因式分解是低效的NP算法,用这个来判定质数纯属吃力不讨好。

筛法是用来筛一个范围的数字是不是素数的,不是用来判定单独一个数字是不是素数的。你可能对筛法的适用范围存在严重的误解。

写了一堆AKS,ECPP,miller-rabin的内容, 然后我发现知乎上已经有现成的完美回答了,稍微扩展一下就是对这个领域的一篇小综述:

具体算法实现可以自己百度,这里随便找了一份代码:

就算只分解到平方根那么大怕不是也得几年

题主显然对指数级的威力缺乏理解,实际上用你的这个算法,算到宇宙毁灭也算不出来。

对一个两百位的大数字遍历算因式分解

ECPP已经可以判定数万位的数字是不是质数了,区区200位在现代算法和计算机的威力下真的什么也不是。你用来发知乎的手机也能判定数千位的数字是不是质数




  

相关话题

  如何用数论证明 3^x+4^x=5^x 只有一个实数解? 
  如何用初等数论知识证明26是唯一夹在一个平方数和立方数间的正整数? 
  n! 和 n²,哪个更大呢? 
  为什么n为素数时,n能整除2^n - 2,怎么证明? 
  一个正常智商的人终其一生能够理解费马大定理的证明吗? 
  是不是任意一个无理数都对应一个三角和描述? 
  正整数 (m, n) 如何取值使得 m*n-pi*n^2 的绝对值最小? 
  一个正常智商的人终其一生能够理解费马大定理的证明吗? 
  黎曼猜想具体是如何推出素数定理的广义形式的? 
  是否大于等于5的质数都能写成质数+质数+1? 

前一个讨论
如果在1941.3.1日的斯大林突然收到准确消息,德国将会在6.22突袭苏联,如何避免巴巴罗萨的溃败?
下一个讨论
站在 2020 年回看,如何评价 Python 2 到 3 的升级?





© 2025-05-03 - tinynew.org. All Rights Reserved.
© 2025-05-03 - tinynew.org. 保留所有权利