gotutiyan’s blog

競技プログラミングをやったりopenframeworksでお絵かきをしたりしています。

AOJ-ICPC 「Prime Gap」

問題
Prime Gap | Aizu Online Judge

素数を並べた要素数10^5の数列 { 2,3,5,7,11,13,17....1299709 } がある。この時、「prime gap」を考える。例えば、10であるときには、数列の[7 11]の間に入るので、prime gap は11-7=4となる。

解説
上の問題文は要約です。詳しくは翻訳に突っ込むなりしてください。
まず、入力が素数の時はprime gapは0です。
そうでない時は、入力の値が数列のどこに入るのかを調べます。厳密には、入力x、素数配列をprimeとした時、prime[i] < x < prime[i+1]となるようなiが存在するので、prime[i+1]-prime[i]を出力します。この時のiの求め方ですが、素直にforを回しても良いですが、lower_boundを使うと楽です。

lower_bound(検索する配列の先頭ポインタ, 後ろのポインタ, 検索したい値)

これを使うことで、指定された要素以上の値が現れる最初の位置のイテレータを取得できます。

これにより取得したイテレータと、その1つ後ろのイテレータに格納された要素の差を出力すればこの問題は解けました。

#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(int)j;i<(int)k;i++)
#define itrep(i,x) for(auto i=(x).begin(); i!=(x).end();i++)
#define Sort(x) sort((x).begin(),(x).end())
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define vi vector<int>
#define INF (int)1e9
#define INFL 1e18
#define MOD 1000000007
#define pb push_back
#define MP make_pair
#define PI 3.1415926535
typedef long long int ll;
//typedef std::pair<int,int> P;
int D=1;
int dx[4]={0,1,0,-1},dy[4]={-1,0,1,0};

using namespace std;

//素数判定関数
bool isPrime(int x){
    if(x==1)return false;
    if(x==2)return true;
    if(x%2==0)return false;
    rep(i,3,sqrt(x)+1){
        if(x%i==0)return false;
    }
    return true;
}

int main(){
    vector<int> prime; //素数テーブル
    prime.pb(2);
    rep(i,3,1299710){
        if(isPrime(i)){
            prime.pb(i);
        }
    }
    
    int x;
    while(cin>>x&&x){
        if(isPrime(x)){  //xが素数ならprime gapは0
            cout<<0<<endl;
            continue;
        }
        auto it=lower_bound(all(prime),x);
        cout<<*it-*(it-1)<<endl; //素数で無ければ、差を出力
    }
    
    return 0;
}