程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 3518 有序的都可以二分查找

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;
}