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