AOJ 1276,PKU 3518 Prime Gap

問題概要

ある数値Nに対しNが素数なら0，素数ではないなら，Nより大きい最小の素数とNより小さい最大の素数の差を出力せよ

解法

篩を使って範囲内の全素数を求めて配列に答を代入していく．

実装(C++)

#include <iostream>
#include <vector>
using namespace std;
vector<bool> eratosthenes_sieve(int n){
	vector<bool> res(n+1);
	res[0]=res[1]=false;res[2]=true;
	int i,j;
	for(i=3;i<=n;i+=2){
		if(i*i<=n){
			if(res[i]==false){
				for(j=i+i+i;j<=n;j+=i+i){
					res[j]=true;
				}
			}
		}
		res[i]=!res[i];
	}
	return res;
}

vector<int> prime_list(const vector<bool>& isprime){
	vector<int> res;if(isprime.size()<=2)return res;
	res.push_back(2);
	for(unsigned int i=3;i<isprime.size();i+=2)
		if(isprime[i])res.push_back(i);
	return res;
}
vector<int> prime_list(int n){
	return prime_list(eratosthenes_sieve(n));
}

vector<int> a(1299710);
int main() {
	vector<int> pl=prime_list(1299710);
	for(int i=0;i<(int)pl.size()-1;i++){
		for(int j=pl[i]+1;j<pl[i+1];j++){
			a[j]=pl[i+1]-pl[i];
		}
	}
	int n;
	for(;cin>>n,n;){
		cout<<a[n]<<endl;
	}
	return 0;
}