如何判断一个超级大的数是不是素数？ 第1页
1
assptiger 网友的相关建议:
现在知乎已经沦落到贴一堆latex就可以骗赞了吗？看来下次我写个数学公式自动生成器就能有赞了？
贴latex就算了，好歹只是不懂强答，那几个民科又是怎么回事？
质量还不如维基百科呢……
素数判定是一个P问题，而且已经有了好几种实用的判定算法。
你说的因式分解是低效的NP算法，用这个来判定质数纯属吃力不讨好。
筛法是用来筛一个范围的数字是不是素数的，不是用来判定单独一个数字是不是素数的。你可能对筛法的适用范围存在严重的误解。
写了一堆AKS，ECPP，miller-rabin的内容， 然后我发现知乎上已经有现成的完美回答了，稍微扩展一下就是对这个领域的一篇小综述：
具体算法实现可以自己百度，这里随便找了一份代码：
就算只分解到平方根那么大怕不是也得几年
题主显然对指数级的威力缺乏理解，实际上用你的这个算法，算到宇宙毁灭也算不出来。
对一个两百位的大数字遍历算因式分解
ECPP已经可以判定数万位的数字是不是质数了，区区200位在现代算法和计算机的威力下真的什么也不是。你用来发知乎的手机也能判定数千位的数字是不是质数
1
相关话题
如何看待 arXiv2111.02792 对黎曼猜想的证明？这样的广义斐波那契数列能得到如下的单调性结果吗？
前N个整数的最小公倍数有没有近似公式？
是否存在一不等于0的完全平方数，使得它成为连续质数个整数之积？
请通俗易懂地讲讲什么是素数（质数）？
请问是质数更多还是合数更多还是一样多？
如何证明两个有理数平方和不能为 7？
可不可以将所有无理数全都用 有理数·π 来表示？
如何判断任意无理数的无理数次方是否为有理数或是无理数？
哥德巴赫猜想可不可以这样想？
相关的话题
将一个大于等于3的数分成三个正整数相加有多少种分法？从1到1亿有一亿个整数，是否有可能存在一个整数，从来没有人读过它?
是否存在一不等于0的完全平方数，使得它成为连续质数个整数之积？
整数多还是偶数多？
整数多还是偶数多？
如何证明存在 1000 个连续的正整数中恰好有五个素数？
世界上存在周长为整数，半径也是整数的圆吗？
黎曼猜想具体是如何推出素数定理的广义形式的？
如何简洁地证明二次互反律？有哪些具体应用？
勒让德猜想被证明了吗？
如果我能证明哥德巴赫猜想，也就是1+1，那么写成文章发在知乎应该成果不会被它人盗取吧？
从1到1亿有一亿个整数，是否有可能存在一个整数，从来没有人读过它?
在你不能证明e+π是无理数之前，有人问你这是有理数还是无理数，你选什么（看补充）？
如何证明不存在这样的X和Y使得下等式成立?
你相信质数会有递推表达式，或者有简单的几何形态吗？
哥德巴赫猜想可不可以这样想？
除了 3，4，5 以外是否还有别的三角形，它的三条边是连续自然数，它的面积也是自然数？
设σ(n)是n的所有正因数之和，如何证明存在无数个正整数n使得σ(n)是完全平方数?
如何证明 1²+2²+…+n² 为平方数的解只有 n＝1 或 n＝24？
民科是否很少攻击数学？
到底有没有素数公式？素数公式的意义有多大？
3³+4³+5³=6³，只是个巧合吗?
请问a^2+2*b^2+3*c^2=20*d^2的所有整数解是什么？
可以找到两个质数，他们的比值最接近 π 吗？
假如数学没有了自然数的概念及其性质会怎样？
除了 3，4，5 以外是否还有别的三角形，它的三条边是连续自然数，它的面积也是自然数？
如何看待据称菲尔兹奖得主 Atiyah 所写的五页黎曼猜想证明？
级数求积：是否有一般的收敛判别法？以及实例∏[p是素数] p/(p-1) 是否收敛?
如何证明下面的整除关系成立？
证明「哥德巴赫猜想」到底有多难？