void getprime(int n) //n是素数筛选区间
{
int i , j
bool flag[N]
memset ( flag , true , sizeof ( flag ) )
int count = 0 //记录找到的素数个数
for( i=2 i<=n i++ )
{
if ( flag[i] ) prime[++count]=i //未被筛掉的就是素数
for( j=1 j<=count && i*prime[j] <= n j++) // prime[j]表示第j个素数
{
flag[ i*prime[j] ] = false //i*prime[j]表示被i筛掉的
if( i%prime[j]==0 ) break
}
}
}
这个算法是一个很快的算法，详细的解释是举例：
i=6的时候，prime[ ]={2,3,5}
第一次6筛掉了6*2=12，然后判断6%2==2，break；假设循环没有break，接着6即将筛6*3=18，而事实上18是被9筛掉的。
统一化分析：
不妨设i=p*r (p<r),执行break是因为i%p==0，故此时i筛掉的是x1=i*p=(p*r)*p；如果i可以筛掉x1后面的数x2，x2=i*q=(p*r)*q
由x2>x1-》q>p那么x2可以写成x2=(q*r)*p,由于 q*r>i ,所以x2一定可以被i之后某个数字(q*r)筛掉，就不需要用i去筛掉。
#include <stdio.h>
int main()
{
int a=0
int num=0
int i
printf("输入一个整数：")
scanf("%d",&num)
for(i=2i<numi++){
if(num%i==0){
a++
}
}
if(a==0){
printf("%d是素数。\n", num)
}else{
printf("%d不是素数。\n", num)
}
return 0
}
扩展资料：
质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数。
基本算法：若 k%m==0 则说明 k 不是素数。
判断整数n是否为素数——采用枚举法求解。
采用枚举算法解题的基本思路：
（1）确定枚举对象、枚举范围和判定条件；
（2）枚举可能的解，验证是否是问题的解。
枚举算法的一般结构：while循环。
参考资料来源：百度百科-枚举法
