C语言中素数怎么求

Question

如题所述

Answer 1

素数求法有很多种。。如果不要求时间暴力尝试是可以的。用算法的话个人认为还是用这个方法最快最好，就是把不是素数的数字排除，剩下的就是素数了。这个程序蛮简单的。。你看看能不能理解ps：这是我们acm培训的内容，很难得哦

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去筛掉。