読者です 読者をやめる 読者になる 読者になる

AOJ0150 Twin Prime

解法
メモ化した愚直な素数判定。エラトステネスの篩でも良い。

反省
はじめnの制約を見てなかったので愚直のisPrimeでTLEだったが、実行時間は4秒ほどだった。これならメモ化で十分かとなり、コードを書き直す必要はなかった。

#include<bits/stdc++.h>
using namespace std;
int n;
int memo[10001];
bool isPrime(int x) {
  if(memo[x]>=0) return memo[x];
  for(int i=2; i*i<=n; i++) {
    if(x % i == 0) return memo[x] = 0;
  }
  return memo[x] = 1;
}
 
int main() {
  fill(memo, memo+10000, -1);
  while(cin >> n && n) {
    int mx = 5;
    for(int i=2; i<=n-2 ; i++) {
      if((isPrime(i)&isPrime(i+2)) == 1) {
    mx = i;
      }
    }
    cout << mx << ' ' << mx+2 << endl;
  }
   
  return 0;
}