筛选法<求素数表>

2018-02-02 19:51:58来源:cnblogs.com作者:Kannyi人点击

分享

如果题目的数据规模较大,常规地逐个判断素数的方法行不通,可以使用筛选法进行预处理,将所有素数一次性求出并存入数组中。

筛选法求素数的主要思想如下:

 (1)将1~N的所有数都标记为素数,0表示素数,1表示非素数。

 (2)1不是素数,也不是合数,标记为1。

 (3)2是素数,保留。但比2大的所有2的倍数都标记为1,直到大于N为止。

 (4)继续寻找素数标记,找到3,将其保留,但比3大的所有3的倍数都标记为,直到大于N为止。

  ……

tip:如果数组声明为全局变量,那么数组会初始化为全0,所以我没有定义int a[N]={0};

#include "stdio.h"    #define N 1000001    int a[N];                     //将1~N中的所有数都先标记为0,初始时均标记为素数,0是素数,1是非素数    void list()    {        int t,i;        a[0]=a[1]=1;              //素数从2开始算,非素数标记为1        for(i=2;i<N/2;i++)        //最多只要遍历到N/2即可,N/2一定非素数        {            if(a[i]==0)           //如果找到一个素数            {                t=2*i;            //先从i的2倍开始标记                while(t<=N)                {                    a[t]=1;       //标记为非素数                    t+=i;         //i的3倍、4倍、5倍......(≤N)都标记为1(非素数)                }            }        }    }    int main()    {        list();                   //生成素数表        int i;        for(i=1;i<=N;i++)        {            if(a[i]==0)            printf("%d/n",i);        }        return 0;    }    

相关文章

    无相关信息

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台