本文共 1499 字，大约阅读时间需要 4 分钟。

<1>方法一

//判断是否是一个素数int IsPrime(int a){	//0,1，负数都是非素数	if(a <= 1){		return 0;	}	//计算枚举上界，为防止double值带来的精度损失，所以采用根号值取整后再加1，即宁愿多枚举一个，也不愿少枚举一个数	int bound = (int)sqrt(a) + 1;	for(int i = 2;i < bound;i++){		//依次枚举这些数能否整除x，若能则必不是素数		if(a % i == 0){			return 0;		}	}	return 1;}

<2>方法二

#define MAXSIZE 10001int Mark[MAXSIZE];int prime[MAXSIZE];//判断是否是一个素数  Mark 标记数组 index 素数个数int Prime(){	int index = 0;	memset(Mark,0,sizeof(Mark));	for(int i = 0;i < MAXSIZE;i++){		//已被标记		if(Mark[i] == 1){			continue;		}		else{			//否则得到一个素数			prime[index++] = i;			//标记该素数的倍数为非素数			for(int j = i*i;j < MAXSIZE;j += i){				Mark[j] = 1;			}		}	}	return index;}

<3>方法三

这种方法比较好理解，初始时，假设全部都是素数，当找到一个素数时，显然这个素数乘上另外一个数之后都是合数

把这些合数都筛掉，即算法名字的由来。但仔细分析能发现，这种方法会造成重复筛除合数，影响效率。

比如10，在i=2的时候，k=2*15筛了一次；在i=5，k=5*6 的时候又筛了一次。所以，也就有了快速线性筛法。

int Mark[MAXSIZE];int prime[MAXSIZE];//判断是否是一个素数  Mark 标记数组 index 素数个数int Prime(){	int index = 0;	memset(Mark,0,sizeof(Mark));    for(int i = 2; i < MAXSIZE; i++)    {		//如果未标记则得到一个素数		if(Mark[i] == 0){			prime[index++] = i;		}		//标记目前得到的素数的i倍为非素数		for(int j = 0; j < index && prime[j] * i < MAXSIZE; j++)        {			Mark[i * prime[j]] = 1;			if(i % prime[j] == 0){                break;			}        }    }	return index;}

利用了每个合数必有一个最小素因子。每个合数仅被它的最小素因子筛去正好一次。所以为线性时间。 代码中体现在： if(i%prime[j]==0)break; prime数组 中的素数是递增的,当 i 能整除 prime[j]，那么 i*prime[j+1] 这个合数肯定被 prime[j] 乘以某个数筛掉。 因为i中含有prime[j], prime[j] 比 prime[j+1] 小。接下去的素数同理。所以不用筛下去了。 在满足i%prme[j]==0这个条件之前以及第一次满足改条件时,pr[j]必定是pr[j]*i的最小因子。

参考博文：

习题练习：

转载地址：http://wucsi.baihongyu.com/