高分求大素数算法

Question

to 2002pine(在深圳真的很累)     这种东西用递归的唯一下场就是机器死机,不现实的,谢谢关注    我再顶!!!!!
谢谢大家关注

Answer 1

数论上有两条定理：
1.设n是一个正合数，p是n的一个大于1的最小正因子，则p一定是素数，且小等于n的平方根
2.设n是一个正整数，如果对所有的素数P小等于n的平方根，都有P不能被n整除，则n一定是素数
基于这两个定理，有一种叫做埃拉托斯散筛法
算法语言描述为：
对于任意给定正整数N，要求出所有不超过Ｎ的素数，我们列出Ｎ个整数，从中删除小于等于N平方根的所有素数p[1],............p[k]的倍数，然后依次删除
　ｐ[1]的倍数　：2p[1],........[N/p[1]]p[1]
   .
   .
   .
   .
   p[k]的倍数:  2p[k],........[N/p[k]]p[k]
如下的整数（不包括１）就是所要求的不超过N的素数
参考一下吧