poj2689素数问题

打算重新刷一下数论题，忘了很多了，水平也很差，此题入手就不顺了，刷了一个早上，只是一个简单

的素数应用罢了。题意：找出区间长度不超过10^6的最近的素数和最远的素数（相邻的），

算法：数在int范围内，不可能全部一次筛出，所以先筛出50000以内的质数，其他整数（若是合数）必然

至少含有一个50000以内的质因子，所以，对每次区间，再筛，筛去区间中这些质数的倍数即可。

未1A原因：

1，题意要看清！

2，注意细节问题!以及特殊情况！

3.注意边界！虽然是整数范围，刚好在上界时候在for里循环再加的话就越界了，无法判断！

#include<iostream>  //49ms

#include<cstdio>

#include<vector>

#include<cstring>

using namespace std;

bool notpri[50001]; vector<int>pri;

long long f,l;

void getpri()      //先筛出部分质数

{

    notpri[1]=1;

    for(int i=2;i<=50000;i++)

      {

          while(i<=50000&¬pri[i]==1)i++;

          pri.push_back(i);

         for(int j=2*i;j<50001;j=j+i)

              notpri[j]=1;

      }

}

int nowpri[1000001];        //将区间f,l平移到0--l-f。

int main()

{

    getpri();

    while(~scanf("%lld%lld",&f,&l))

    {

        while(f<2)f++;      //排除1的情况

        for(long long i=f;i<=l;i++)  //初始化

         {

             nowpri[i-f]=0;

         }

        int len=pri.size();

        for(int i=0;i<len;i++)       //筛去l--f之间的合数

        {

            long long start=f+(pri[i]-f%pri[i]);

    if(f%pri[i]==0)start-=pri[i];        //起点注意一下，细节

            if(start==pri[i])start+=pri[i];

            for(long long j=start;j<=l;j=j+pri[i])

                  nowpri[j-f]=1;             //j is not prime

        }

        int dis=0;

        int  mindis=1000001;int maxdis=-1;

        long long  maxi1=0,maxi2=0,mini2=0,mini1=0;

        int mark1=1;long long pre=0;

        for(long long i=f;i<=l;i++)  //距离统计一下

        {

            if(nowpri[i-f]==0)

           {

               if(mark1)

               {

                   mark1=0;pre=i;maxi1=maxi2=i;mini1=mini2=i;dis=1;continue;

               }

               if(dis>maxdis)

               {

                   maxdis=dis;maxi1=pre;maxi2=i;

               }

               if(dis<mindis)

               {

                   mindis=dis;mini1=pre;mini2=i;

               }

              pre=i; dis=0;

           }

           dis++;

        }

        if(maxdis<0)

          printf("There are no adjacent primes.\n");

       else

         printf("%lld,%lld are closest, %lld,%lld are most distant.\n",mini1,mini2,maxi1,maxi2);

    }

    return 0;

}

巴特西

poj2689素数问题

最新文章

热门文章