欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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 

素数筛选可以分成两种:普通筛,欧拉筛。这里主要介绍普通筛。

1.素数筛选

#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文件

下一篇: