POJ 2689 Prime Distance

题目链接~~>

做题感悟：这题是在学习了区间筛法后才做的，学习了区间筛素数后，这题真 so easy !

解题思路：可以用两次筛法，也可以直接用区间平移。

代码：

      #include<stdio.h>
      #include<iostream>
      #include<map>
      #include<stack>
      #include<string>
      #include<string.h>
      #include<stdlib.h>
      #include<math.h>
      #include<vector>
      #include<queue>
      #include<algorithm>
      using namespace std ;
      #define LEN sizeof(struct node)
      #define lld long long int
      const double PI = 3.1415926535898 ;
      const double INF = 99999999 ;
      const long long  mod= 1000 ;
      const int MX = 1000005 ;
      bool is_prime[MX] ;
      int prime[MX],num ;
      void search_prime(int L,int U)
      {
       num=0 ;
      int n=sqrt(1.0*U),j ;
      int d=U-L+1 ; // 区间长度
      memset(is_prime,false,sizeof(is_prime)) ;// 先默认全部为素数
      for(int i=( L%2 != 0 ) ;i<d ;i+=2) // 把区间中的偶数筛掉
       is_prime[i]=true ;
      for(int i=3 ;i<=n ;i+=2)
       {
      if(i>L&&is_prime[i-L])// 如果 i 大于 L且is_prime[i-l] 为真则必为合数
      continue ;
       j=(L/i)*i ;// j 为最接近L 的和数且为 i的倍数
      if(j<L)
       j+=i ;
      if(j==i)  j+=i ;
       j-=L ;
      for( ;j<d ;j+=i) // j每次加 i 均为合数 ：j=(L/i)*i+i+i……
       is_prime[j]=true ;
       }
      if(L<=1)  is_prime[1-L]=true ;// 0 1 均不是素数
      if(L<=2)  is_prime[2-L]=false ;
      for(int i=0 ;i<d ;i++)
      if(!is_prime[i])
       prime[num++]=i+L ;
      }
      void find()
      {
      int min=9999999,max=0 ;
      int a1=-1,a2=-1,a3=-1,a4=-1 ;
      for(int i=1 ;i<num ;i++)
       {
      int mx=prime[i]-prime[i-1] ;
      if(mx<min)
       {
       a1=prime[i-1] ;
       a2=prime[i] ;
       min=mx ;
       }
      if(mx>max)
       {
       a3=prime[i-1] ;
       a4=prime[i] ;
       max=mx ;
       }
       }
      if(a1==-1)
      printf("There are no adjacent primes.\n") ;
      else printf("%d,%d are closest, %d,%d are most distant.\n",a1,a2,a3,a4) ;
      }
      int main()
      {
      int L,U ;
      while(~scanf("%d%d",&L,&U))
       {
       search_prime(L,U) ;
       find() ;
       }
      return 0 ;
      }
  
 

代码（二次筛法）：

      #include<stdio.h>
      #include<iostream>
      #include<map>
      #include<stack>
      #include<string>
      #include<string.h>
      #include<stdlib.h>
      #include<math.h>
      #include<vector>
      #include<queue>
      #include<algorithm>
      using namespace std ;
      #define LEN sizeof(struct node)
      #define lld long long int
      const double PI = 3.1415926535898 ;
      const double INF = 99999999 ;
      const long long  mod= 1000 ;
      const int MX = 1000005 ;
      int num=0 ;
      bool is_prime[MX] ;
      __int64 prime[MX] ;
      __int64 prime2[MX] ;
      void init() // 用筛法筛出第一批素数，用于筛指定区间的素数
      {
       num=0 ;
      memset(is_prime,false,sizeof(is_prime)) ;
      for(__int64 i=2 ;i<MX ;i++)
       {
      if(!is_prime[i])
       prime[num++]=i ;
      for(int j=0 ;j<num&&i*prime[j]<MX ;j++)
       {
       is_prime[i*prime[j]]=true ;
      if(i%prime[j]==0)
      break ;
       }
       }
      }
      void search_prime(__int64 L,__int64 U)
      {
      memset(is_prime,false,sizeof(is_prime)) ;
      for(int i=0 ;i<num&&prime[i]*prime[i]<=U ;i++)
       {
       __int64 p=prime[i] ;
      for(__int64 j=(L+p-1)/p ;p<=U/j ;j++)
      if(j>1)
       is_prime[j*p-L]=true ;
       }
      if(L<=1)  is_prime[1-L]=true ;
      if(L<=2)  is_prime[2-L]=false ;// 巧妙
      int nx=0 ;
      for(__int64 i=L ;i<=U ;i++)
      if(!is_prime[i-L])
       prime2[nx++]=i ; // 存区间的素数
       __int64 min=99999999,max=0,a1=-1,a2=-1,a3=-1,a4=-1 ;
      for(int i=1 ;i<nx ;i++)  // 寻找答案
       {
       __int64 mx=prime2[i]-prime2[i-1] ;
      if(min>mx)
       {
       a1=prime2[i-1] ;
       a2=prime2[i] ;
       min=mx ;
       }
      if(max<mx)
       {
       a3=prime2[i-1] ;
       a4=prime2[i] ;
       max=mx ;
       }
       }
      if(a1!=-1)
      printf("%I64d,%I64d are closest, %I64d,%I64d are most distant.\n",a1,a2,a3,a4) ;
      else
      printf("There are no adjacent primes.\n") ;
      }
      int main()
      {
       __int64 L,U ;
       init() ;
      while(~scanf("%I64d%I64d",&L,&U))
       {
       search_prime(L,U) ;
       }
      return 0 ;
      }
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/22647091