AOJ 1004

簡単かと思ったけど意外と手こずってしまった．
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1004
入力 n に対して，1 から n までの列とそれをひっくり返した列 (n から 1 まで) を重ねた上下をペアとして，ふたつとも素数であるようなペアの数を数える．
最初は素数を判定させる関数を作っていちいちそれに放り込む作戦をとったが，時間切れになってしまうので boolean 型の配列そのまま使った．

#include <iostream>
using namespace std;

void prime();
bool num[10001];

int main(){
	int m, count;
	prime();
	while(cin >> m){
		count = 0;
		for(int i = 1; i <= m; i++){
			if(num[i] && num[m - i + 1]){
				count++;
			}
		}
		cout << count << endl;
	}
	return 0;
}

void prime(){
	for(int i = 0; i < 10001; i++){
		num[i] = true;
    	}
    	num[0] = false;
    	num[1] = false;
	for(int i = 2; i <= 100; i++){
        	for(int j = i*2; j <= 10001; j += i){
            		if(!num[j]){
                		continue;
            		}
            		num[j] = false;
        	}
    	}
}

素数を判定するプログラムはたまに必要になるのでメモしておく．
とりあえず 1 000 000 以下の素数について (AOJ 0009 の使い回しなので)．

#include <iostream>
using namespace std;

int main(){
	int n;
	bool num[1000001];
	for(int i = 0; i < 1000001; i++){
		num[i] = true;
	}
	num[0] = false;
	num[1] = false;
	for(int i = 2; i <= 1000; i++){
		for(int j = i * 2; j <= 1000000; j += i){
			if(!num[j]){
				continue;
			}
			num[j] = false;
		}
	}
	while(cin >> n){
		if(num[n]){
			cout << n << " is prime." << endl;
		}
		else{
			cout << n << " is not prime." << endl;
		}
	}
	return 0;
}