如何判断一个超级大的数是不是素数？ 第1页
1
assptiger 网友的相关建议:
现在知乎已经沦落到贴一堆latex就可以骗赞了吗？看来下次我写个数学公式自动生成器就能有赞了？
贴latex就算了，好歹只是不懂强答，那几个民科又是怎么回事？
质量还不如维基百科呢……
素数判定是一个P问题，而且已经有了好几种实用的判定算法。
你说的因式分解是低效的NP算法，用这个来判定质数纯属吃力不讨好。
筛法是用来筛一个范围的数字是不是素数的，不是用来判定单独一个数字是不是素数的。你可能对筛法的适用范围存在严重的误解。
写了一堆AKS，ECPP，miller-rabin的内容， 然后我发现知乎上已经有现成的完美回答了，稍微扩展一下就是对这个领域的一篇小综述：
具体算法实现可以自己百度，这里随便找了一份代码：
就算只分解到平方根那么大怕不是也得几年
题主显然对指数级的威力缺乏理解，实际上用你的这个算法，算到宇宙毁灭也算不出来。
对一个两百位的大数字遍历算因式分解
ECPP已经可以判定数万位的数字是不是质数了，区区200位在现代算法和计算机的威力下真的什么也不是。你用来发知乎的手机也能判定数千位的数字是不是质数
1
相关话题
如何证明有理数加法群不是有限生成群？如果有一天上帝给了数学家素数的通项公式，这会对数学界有什么影响？
费马大定理有初等证明吗？百度文库上有的是4页有的是2页，但看着不靠铺。
a,b,c>0，且abc=1，怎样证明1/√(1＋8a)＋1/√(1＋8b)＋1/√(1＋8c)≧1？
如何在冰雹猜想上做出点成绩?
「只要整数的各个位数之和是 3 的倍数，那么这个整数就一定是 3 的倍数」是如何证明的？
拉马努金的那些壮观的公式，都是怎么发现的？
n的正因子个数d(n)有没有上界公式？
「素数」和「合数」算反义词吗？
只用高中数学知识水平能解出哥德巴赫猜想吗？
相关的话题
请问a^2+2*b^2+3*c^2=20*d^2的所有整数解是什么？如何看待几何数论（geometry of numbers）这一数论分支？
是否存在一个次数不低于 2 的整系数多项式，在任何素数处的取值都是素数？
如何在冰雹猜想上做出点成绩?
如何编程判断一个数是否是质数？
设σ(n)是n的所有正因数之和，如何证明存在无数个正整数n使得σ(n)是完全平方数?
(a+b)!/(a!b!) 的结果一定是整数吗？如果是，如何证明？
任何自然数都能用包含「1、1、4、5、1、4」这 6 个数字的式子表示吗？
关于p进数域？
你相信质数会有递推表达式，或者有简单的几何形态吗？
是否大于等于5的质数都能写成质数+质数+1？
如何证明2的n次方≤（n+1）！，对于所有正整数n？
椭圆曲线群结构结合律证明有没有不爆算的巧妙证明？
可以找到两个质数，他们的比值最接近 π 吗？
关于p进数域？
对于 3 和 4 之间的整数 Bleem，你怎么看？
请问费马大定理写成方程形式是否可以证明？
如何证明f（n）=n^2+n+1，则使f（n）为质数的n的值有无数个？
存不存在连续的三个奇数都是素数（3，5，7 除外）？如果不存在又是为什么？
是不是任意一个无理数都对应一个三角和描述？
到底是奇数多还是偶数多？
如何证明任意比2更大的偶数都是两个素数之和？
如何严格证明斐波那契数列的这两个性质？
正整数真的和自然数一样多么？
到底有没有素数公式？素数公式的意义有多大？
任给N个连续的整数，是否能从中找到一些数（至少一个），使得它们加起来是N(N+1)/2的倍数？
存不存在连续的三个奇数都是素数（3，5，7 除外）？如果不存在又是为什么？
证明在方程 20X^2-19Y^2=2019 中X与Y没有整数解?
如何看待中国矿业大学杨小军研究员宣称自己解决黎曼猜想？
有理数a/b的乘法为什么能先定义下来，为什么不怕会有问题?