如何判断一个超级大的数是不是素数？ 第1页
1
assptiger 网友的相关建议:
现在知乎已经沦落到贴一堆latex就可以骗赞了吗？看来下次我写个数学公式自动生成器就能有赞了？
贴latex就算了，好歹只是不懂强答，那几个民科又是怎么回事？
质量还不如维基百科呢……
素数判定是一个P问题，而且已经有了好几种实用的判定算法。
你说的因式分解是低效的NP算法，用这个来判定质数纯属吃力不讨好。
筛法是用来筛一个范围的数字是不是素数的，不是用来判定单独一个数字是不是素数的。你可能对筛法的适用范围存在严重的误解。
写了一堆AKS，ECPP，miller-rabin的内容， 然后我发现知乎上已经有现成的完美回答了，稍微扩展一下就是对这个领域的一篇小综述：
具体算法实现可以自己百度，这里随便找了一份代码：
就算只分解到平方根那么大怕不是也得几年
题主显然对指数级的威力缺乏理解，实际上用你的这个算法，算到宇宙毁灭也算不出来。
对一个两百位的大数字遍历算因式分解
ECPP已经可以判定数万位的数字是不是质数了，区区200位在现代算法和计算机的威力下真的什么也不是。你用来发知乎的手机也能判定数千位的数字是不是质数
1
相关话题
如何证明 1²+2²+…+n² 为平方数的解只有 n＝1 或 n＝24？为什么费马大定理在数学史上的地位如此重要？
如何证明不定方程是否有解?
除了 1 和 144，还有哪个斐波那契数是平方数?
如何证明 1^2021＋2^2021＋…＋1000^2021 能被 7、11、13 整除？
(a+b)!/(a!b!) 的结果一定是整数吗？如果是，如何证明？
高斯素数有类似于素数定理的分布律吗？
素数的 Willans 公式是否正确？
任取两个大于 2 的整数，其互质的概率是多少？
如何快速判断一个数可被 7 整除？
相关的话题
怎样证明根号 3 是无理数？解决考拉兹猜想，能拿菲尔茨奖吗?
有理数a/b的乘法为什么能先定义下来，为什么不怕会有问题?
高斯素数有类似于素数定理的分布律吗？
为什么前N个自然数的最小公倍数约等于e^N?
如何证明存在 1000 个连续的正整数中恰好有五个素数？
数论方向的研究生前景如何？
如何证明将任意3的倍数各数位数字立方求和，重复数次后得到固定数值153?
请问是质数更多还是合数更多还是一样多？
如何看待京都大学的望月新一教授证明「ABC 猜想」，发表在其主编的期刊上？
Lagrange 如何用连分数理论推导出一次同余方程的通解？
证明了黎曼猜想就能马上得到素数公式吗？
怎么说明质数有无限个？
为什么 1 不能被认为是质数？
请问a^2+2*b^2+3*c^2=20*d^2的所有整数解是什么？
陶哲轩能完整地看懂费马大定理的证明吗？
如何证明一个无理数的整数倍数的小数部分在（0，1）上均匀分布？
P是素数，(2^2p)-3一定是素数吗？
为什么张益唐的论文没被数学年刊忽视掉？
怎样证明根号 3 是无理数？
如何判断任意无理数的无理数次方是否为有理数或是无理数？
一个数列是柯西列也是整数列，如何证明其收敛于整数?
为什么有理数 1/49 看起来这么像是个无限不循环小数？循环节在哪里？
有理数旁边是无理数还是有理数，无理数旁边是有理数还是无理数？
陈景润是如何证明「1＋2」的？
4≤5，这个不等式是否正确？
如何证明非零自然数的平方的倒数和为π^2/6?
任取两个大于 2 的整数，其互质的概率是多少？
全世界的数学家能在18天内找到质数排列规律么？
素数的 Willans 公式是否正确？