如何判断一个超级大的数是不是素数？ 第1页
1
assptiger 网友的相关建议:
现在知乎已经沦落到贴一堆latex就可以骗赞了吗？看来下次我写个数学公式自动生成器就能有赞了？
贴latex就算了，好歹只是不懂强答，那几个民科又是怎么回事？
质量还不如维基百科呢……
素数判定是一个P问题，而且已经有了好几种实用的判定算法。
你说的因式分解是低效的NP算法，用这个来判定质数纯属吃力不讨好。
筛法是用来筛一个范围的数字是不是素数的，不是用来判定单独一个数字是不是素数的。你可能对筛法的适用范围存在严重的误解。
写了一堆AKS，ECPP，miller-rabin的内容， 然后我发现知乎上已经有现成的完美回答了，稍微扩展一下就是对这个领域的一篇小综述：
具体算法实现可以自己百度，这里随便找了一份代码：
就算只分解到平方根那么大怕不是也得几年
题主显然对指数级的威力缺乏理解，实际上用你的这个算法，算到宇宙毁灭也算不出来。
对一个两百位的大数字遍历算因式分解
ECPP已经可以判定数万位的数字是不是质数了，区区200位在现代算法和计算机的威力下真的什么也不是。你用来发知乎的手机也能判定数千位的数字是不是质数
1
相关话题
是否大于等于5的质数都能写成质数+质数+1？存不存在连续的三个奇数都是素数（3，5，7 除外）？如果不存在又是为什么？
为什么任何整数除以2或5都能除尽，而不一定能被其他质数除尽？
只用高中数学知识水平能解出哥德巴赫猜想吗？
世界上存在周长为整数，半径也是整数的圆吗？
如何看待这位知友提出的这个声称只有他能解的问题？
如何用准确的数学语言证明:两素数分别n次方后还是互素?
质数在生活中有什么用？
如何判断任意无理数的无理数次方是否为有理数或是无理数？
素数的 Willans 公式是否正确？
相关的话题
如何证明f（n）=n^2+n+1，则使f（n）为质数的n的值有无数个？勾股数有有限多组还是无限多组？
数列an（定义an为71^n）是否在an中能找到以任意长度（不小于1）个1为结尾的数（均是正整数）?
这样的广义斐波那契数列能得到如下的单调性结果吗？
如果打算证明黎曼猜想，请问从大一开始应该做什么数学基础准备？
有哪些具有特殊性质的数字？
如何在冰雹猜想上做出点成绩?
有理数a/b的乘法为什么能先定义下来，为什么不怕会有问题?
如何证明对于任意的正整数n，若p整除n^2+n+1，则p模3一定不余2？
为什么任何整数除以2或5都能除尽，而不一定能被其他质数除尽？
如何证明方程 x³＋y³＝2020 没有整数解？
哥德巴赫猜想可不可以这样想？
任给N个连续的整数，是否能从中找到一些数（至少一个），使得它们加起来是N(N+1)/2的倍数？
为什么费马大定理表述起来这么简单，证明却这么复杂？
P是素数，(2^2p)-3一定是素数吗？
比0.000······1更小的非0数，是什么？
如何证明存在 1000 个连续的正整数中恰好有五个素数？
比三大，比四小的整数是存在的吗？
一个数被2除余1，被3除余2，被4除余3，被5除余4，被6除余5，被7整除，这个数是多少？
到底是奇数多还是偶数多？
怎么证明2³²+1不是素数？
为什么说尾数为1、3、7、9的素数个数是基本相同的？
高中生对哥德巴赫猜想的证明有哪些错误？
如何证明存在 1000 个连续的正整数中恰好有五个素数？
请问费马大定理写成方程形式是否可以证明？
请问费马大定理写成方程形式是否可以证明？
任何自然数都能用包含「1、1、4、5、1、4」这 6 个数字的式子表示吗？
4x5的表写入20个不同正整数，相邻数不互质，表中最大的数至少是多少？
如何证明存在 1000 个连续的正整数中恰好有五个素数？
如何证明下面的整除关系成立？