作者Leeng (老千)
看板C_and_CPP
标题Re: [问题] 判断质数等不到所有数都除过就判定了？
时间Sun Aug 30 21:29:33 2009
整理一下
bool isPrime(int N){ //引入问题N
// 要有一些前置防呆
if( N < 2 ) return 0; // 不考虑1以下
if( N == 2 ) return 1; // 2为质数
if( N % 2 == 0 ) return 0; //偶数
//接下来才是运算部分
int M = int(sqrt(N)); //判断N是否为质数，不需要超过根号N
for( int i = 3; i < M; i+=2 ){
if( N % i == 0 ) return 0;
}
return 1;
}
所以基本上质数判断是(根号N)量级
另外我有试着制作质数表，就是从3开始+2往上跑，是质数就写到txt
扣除一些初始值(2,3,5等)，判断为质数的方法改为从txt里面捞
(不晓得这样跟 %(i+2)哪个比较快 )
累计到八位数就要一百多MB = =
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.230.238.233
※ 编辑: Leeng 来自: 61.230.238.233 (08/30 21:31)
1F：推 VictorTom:後来想到, 考虑浮点误差, sqrt完可能还是加个0.5保险Orz 08/30 21:31
2F：推 LPH66:更好的是不用 sqrt 改成 i*i<=M 即可 08/30 21:36
3F：→ LPH66: i*i<=N 08/30 21:36
4F：→ Leeng:2F说的 在上一篇推文提出的反驳是i*i<=N在每个回圈都要计算 08/30 21:39
5F：→ Leeng:直接给定上限只要做一次就好了 08/30 21:39
6F：→ Leeng:除非是制作大量质数表，每次N都不一样 而要呼叫多次math.h 08/30 21:40
7F：→ Leeng:才要放弃sqrt而用i*i<=N 08/30 21:41
8F：→ Leeng:要不然就是编译环境限制下，函数库能省则省吧? 08/30 21:42