如何判断一个超级大的数是不是素数？ 第1页
1
assptiger 网友的相关建议:
现在知乎已经沦落到贴一堆latex就可以骗赞了吗？看来下次我写个数学公式自动生成器就能有赞了？
贴latex就算了，好歹只是不懂强答，那几个民科又是怎么回事？
质量还不如维基百科呢……
素数判定是一个P问题，而且已经有了好几种实用的判定算法。
你说的因式分解是低效的NP算法，用这个来判定质数纯属吃力不讨好。
筛法是用来筛一个范围的数字是不是素数的，不是用来判定单独一个数字是不是素数的。你可能对筛法的适用范围存在严重的误解。
写了一堆AKS，ECPP，miller-rabin的内容， 然后我发现知乎上已经有现成的完美回答了，稍微扩展一下就是对这个领域的一篇小综述：
具体算法实现可以自己百度，这里随便找了一份代码：
就算只分解到平方根那么大怕不是也得几年
题主显然对指数级的威力缺乏理解，实际上用你的这个算法，算到宇宙毁灭也算不出来。
对一个两百位的大数字遍历算因式分解
ECPP已经可以判定数万位的数字是不是质数了，区区200位在现代算法和计算机的威力下真的什么也不是。你用来发知乎的手机也能判定数千位的数字是不是质数
1
相关话题
是否存在一个次数不低于 2 的整系数多项式，在任何素数处的取值都是素数？P是素数，(2^2p)-3一定是素数吗？
1²+2²+…+n²求和公式的推导有哪些方法?
站在一个无穷大的围棋/五子棋盘上的任意格点上，能够看到的格点都放上黑棋，黑棋占格点比例多少？
下面这个关于质数的不等式如何证明？
数列an（定义an为71^n）是否在an中能找到以任意长度（不小于1）个1为结尾的数（均是正整数）?
哥德巴赫的猜想如果被证实，对数学和全人类有什么意义？
陶哲轩能完整地看懂费马大定理的证明吗？
民科是否很少攻击数学？
下面这个关于质数的不等式如何证明？
相关的话题
正整数真的和自然数一样多么？从1到1亿有一亿个整数，是否有可能存在一个整数，从来没有人读过它?
对于任意既约分数，都可以分解成有限个不同奇数的倒数和吗？
如何证明2的n次方≤（n+1）！，对于所有正整数n？
如何证明它不是整数啊?
圆周率π的这个用正切半角表示的无穷级数展开式怎么证明?
自然数和非负整数有什么区别？
任取两个大于 2 的整数，其互质的概率是多少？
如何将无穷级数Σ1/n²写成定积分的形式？
如何证明 不存在两个有理数a、b，使得 a＋√b=³√2？
Shamir秘密共享门限方案当模数为多项式大时，为什么不安全？
黎曼猜想（Riemann hypothesis）是什么？有什么用？
为什么民科对数论情有独钟？
有没有一个数可以既是完美数又是完全平方数？
如何看待π这个无理数？
如何证明不定方程是否有解?
数论方向的研究生前景如何？
如何完成这道数学序列证明题？
如何找到一个10项的非负整数数列，使该数列的任意不超过3项的和不重复，并使数列的最大项最小，并证明?
站在一个无穷大的围棋/五子棋盘上的任意格点上，能够看到的格点都放上黑棋，黑棋占格点比例多少？
如何用准确的数学语言证明:两素数分别n次方后还是互素?
正整数 (m, n) 如何取值使得 m*n-pi*n^2 的绝对值最小？
威尔逊定理中 p=4是一个例外，为什么？是否存在其他非质数的例外？
3，13，1113，3113，2321，221311，223113，222321，下一个数是什么？
请问是质数更多还是合数更多还是一样多？
为何常用偶数进制却少见奇数进制？
2022 这个数字在数学意义上有什么特别的，为什么？
如何用组合数学证明 (n²)! 能被 (n!)^(n＋1) 整除？
如何证明两个有理数平方和不能为 7？
P是素数，(2^2p)-3一定是素数吗？