POJ 3518 有序的都可以二分查找 - c++编程基础

Prime Gap

Time Limit: 5000MS		Memory Limit: 65536K
Total Submissions: 8007		Accepted: 4696

Description

The sequence of n 1 consecutive composite numbers (positive integers that are not prime and not equal to 1) lying between two successive prime numbers p and p + n is called a prime gap of length n. For example, 24, 25, 26, 27, 28 between 23 and 29 is a prime gap of length 6.

Your mission is to write a program to calculate, for a given positive integer k, the length of the prime gap that contains k. For convenience, the length is considered 0 in case no prime gap contains k.

Input

The input is a sequence of lines each of which contains a single positive integer. Each positive integer is greater than 1 and less than or equal to the 100000th prime number, which is 1299709. The end of the input is indicated by a line containing a single zero.

Output

The output should be composed of lines each of which contains a single non-negative integer. It is the length of the prime gap that contains the corresponding positive integer in the input if it is a composite number, or 0 otherwise. No other characters should occur in the output.

Sample Input

Sample Output

题意：就是求这个数两边的素数之差，如果是素数了的话就直接输出0.

思路：先打表再二分答案。

这题搞了好久才过，晕……刚开始找素数表时，数组开太大了不行，开太小也不行，然后哈哈学别人用char数组就可以了，以前还没这么用过……又学到了点有用的东东……

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
              #include 
              
                #include 
               
                 #define PI acos(-1.0) #define eps 1e-6 #define mem(a,b) memset(a,b,sizeof(a)) #define sca(a) scanf("%d",&a) #define pri(a) printf("%d\n",a) #define MM 100005 #define MN 1005 #define INF 10000007 using namespace std; typedef long long ll; int prime[MM],cnt,k,low,high; char is[1299719]; void is_prime() { int i,j,k=1299709; for(i=2;i<=k;i++) if(!is[i]) { prime[cnt++]=i; for(j=i+i;j<=k;j+=i) is[j]=1; } } void gao() { int i,j,l=0,r=cnt,mid; while(l
                
                 >1; if(prime[mid]>k) r=mid; else l=mid+1; } if(prime[l]>k) high=l,low=l-1; else high=l+1,low=l; } int main() { is_prime(); while(sca(k)&&k) { if(!is[k]) puts("0"); else { gao(); pri(prime[high]-prime[low]); } } return 0; }