AOJ_2150 Matsuzaki Number

問題
M(N, P) = Nより大きい2つの素数の和をとることで得られる数を，小さいほうから順に並べたとき，P 番目の数
M(N, P)を求めよ。
0 ≤ N ≤ 100,000
1 ≤ P ≤ 100

解法
はじめにエラストテネスの篩で素数をたくさん求めておく。
Nより大きいP個の素数をみつける。
それらの素数の組み合わせで得られる和を優先度付きキューに入れてソート
P番目に取り出された値が答え。

実装

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

const int MAX_N = 201000;
const int MAX_P = 100;
bool prime[MAX_N];
int matsuzaki(int n, int P){
		int pri[MAX_P]; //nより大きいP個の素数を貯めておく
		priority_queue<int, vector<int>, greater<int> > pque;
		//P個の素数を見つける
		int pri_n = 0;
		for(int i = n + 1; pri_n < P; i++){
				if(prime[i]){
						pri[pri_n] = i;
						pri_n++;
				}
		}
		//P個の素数を組み合わせてできるすべての数を優先度付きキューに
		for(int i = 0; i < P; i++){
				for(int j = i; j < P; j++){
						pque.push(pri[i] + pri[j]);
				}
		}
		//P番目に小さい数を取り出す
		int t;
		for(int i = 0; i < P; i++){
				t = pque.top(); pque.pop();
		}
		return t;
}
int main(){
		int N, P;
		fill(prime, prime + MAX_N, true);
		prime[0] = prime[1] = false;
		for(int i = 2; i * i <= MAX_N; i++){
				if(!prime[i]) continue;
				for(int j = i + i; j < MAX_N; j += i){
						prime[j] = false;
				}
		}
		while(scanf("%d %d", &N, &P)){
				if(N == -1) return 0;
				printf("%d\n", matsuzaki(N, P));
		}
		return 0;
}