AOJ : 0222 - Prime Quadruplet

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0222&lang=jp
日本語なので省略です

アルゴリズム

エラトステネスのふるいによって, あらかじめ素数表を作成しておきます.
あとは, (a-8, a-6, a-2, a) が全て素数となるようなaを, 入力値からマイナスしていきながら見つけます.
(a-8, a-6, a-2, a) にしてるのは, 入力値から順番に, マイナスしながら探索しているためです.

プログラム

#include <iostream>
#include <cstring>
using namespace std;

char p[10000001];

void mkPrime(void){
  memset(p,1,sizeof(p));
  p[0] = p[1] = 0;
  for(int i=2;i<=10000000;i++){
    if(p[i]){
      for(int j=i*2;j<=10000000;j+=i){
        p[j] = 0;
      }
    }
  }
}

int main(void){
  mkPrime();

  int n;

  while(cin>>n && n){
    int i = n;
    while(!(p[i] && p[i-2] && p[i-6] && p[i-8])) i--;
    cout<<i<<endl;
  }

  return 0;
}