1.素数筛选
程序员文章站
2024-03-21 15:01:58
...
素数筛选
编写函数1,判断一个数是否是素数,
主函数中,找出m~n之间的所有素数
Input
整数m n
Output
所有素数
Sample Input
7 20
Sample Output
7 11 13 17 19
素数筛选可以分成两种:普通筛,欧拉筛。这里主要介绍普通筛。
#include<stdio.h>
#include<string.h>
#include<math.h>
const int MAX=1e6+7; //这里MAX必须是一个常量。
int prime[MAX];
void init1 ()
{
memset(prime,0,sizeof(prime));
int n=sqrt(MAX);
prime[1]=1; //这里需要对1进行判定
for(int i=2;i<=n;i++)
if(prime[i]==0)
for(int j=i*i;j<MAX;j+=i)//因为2是素数,所以它的倍数一定不是倍数。
prime[j]=1;
}
下面是整个实现过程:
(init2是将prime数组中标记的素数重新在prime中存入,也可以重新开一个数组来存标记的素数,这个过程类似与欧拉筛,那么就当做替换欧拉筛吧~~嘿嘿)
#include<stdio.h>
#include<string.h>
#include<math.h>
const int MAX=1e6+7;
int prime[MAX];
void init1 ()
{
memset(prime,0,sizeof(prime));
int n=sqrt(MAX);
prime[1]=1;
for(int i=2;i<=n;i++)
if(prime[i]==0)
for(int j=i*i;j<MAX;j+=i)
prime[j]=1;
}
void init2()
{
memset(prime, 0, sizeof(prime));
prime[0] = prime[1] = 1;
for(int i=2; i<=sqrt(MAX); i++)
{
if(!prime[i])
{
for(int j=i*i; j<=MAX; j+=i)
prime[j] = 1;
}
}
for(int i=2, j=0; i<=MAX; i++)
if(!prime[i])
prime[j++] = i;
}
int main()
{
int m,n,i;
init1 ();
//init2 ();
scanf("%d %d",&m,&n);
for(i=m;i<=n;i++)
{
if(prime[i]==0)
printf("%d ",i);
}
return 0;
}
上一篇: Java生成CSV文件