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