AOJ - Problem 1004 : Pair of Primes

AOJ 数論

n個の組(1,n)(2,n-1)(3,n-2) ... (n-1,2)(n,1)について、2つの数字がどちらも素数の組の数を求める問題です。エラトステネスの篩で最初に素数表をつくっておきましょう。

#include <iostream>
using namespace std;

const int MAX = 1000001;
char p[MAX] = {0};

void f(){
	for(int i=2 ; i < MAX ; i++ ) p[i] = 1;
	for(int i=2 ; i*i < MAX ; i++ ){
		if( p[i] ){
			for(int j=i+i ; j < MAX ; j += i ){
				p[j] = 0;
			}
		}
	}
}

int main(){
	int n;
	f();
	while( cin >> n ){
		int ans=0;
		for(int a=1 ; a <= n ; a++ ){
			int b = n + 1 - a;
			if( p[a] && p[b] ) ans++;
		}
		cout << ans << endl;
	}
}