首页 > 代码库 > 素数筛 E - Fermat’s Chirstmas Theorem

素数筛 E - Fermat’s Chirstmas Theorem

#include <iostream>#include <stdio.h>#include <math.h>#include <vector>using namespace std;int a[1000001];int  prime[1000001];int main(){    int k,tt=0;    int p;    a[0]=a[1]=0;    a[2]=1;    for(int i=3;i<=1000000;i++)    {        a[i]=i%2==0?0:1;    }    int t=(int )sqrt(1000000*1.0);    for(int j=3;j<=t;j++)    {        if(a[j])        {            for(int i=j*j;i<1000000;i=i+2*j)              a[i]=0;        }    }    for(int i=1;i<100;i++)    {        if(a[i]) printf("%d ",i);    }    for(int i=2;i<=1000000;i++)    {        if(a[i])        prime[tt++]=i;    }    int L,U;    int  i;    while(scanf("%d%d",&L,&U))    {        k = 0;        p = 0;        if(L == -1 && U == -1)        break;        for(i=0;i<tt;i++)        {            if(prime[i]>=L&&prime[i]<=U)            {                k++;                if((prime[i]-1)%4==0)                p++;            }        }        if(L<=2&&U>=2) p++;        printf("%d %d %d %d\n",L,U,k,p);    }}