AOJ 0222 （Prime Quadruple : 四つ子素数）
【問題】
https://onlinejudge.u-aizu.ac.jp/problems/0222
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0222
【解説】
4つの整数がすべて素数であるかを判定する問題。
nの最大値が10,000,000と大きいため、事前にエラトステネスの篩によりあらかじめ指定した数が素数かどうかを求めておく。その際に愚直に10,000,000までで割っていくとTLEする。10,000,000以下の合成数Xには、ルートX以下の約数が必ず含まれるため（※）、10,000,000のルートまで割った時点で処理を打ち切り、処理時間を短縮する。
先に素数のリストさえ作っておけば、あとは入力されたnから降下していきながら判定していけばよい。この際、nの最小値が13（最小の四つ子素数）であるため、指定されたn以下に四つ子素数が含まれないことは考えなくてよい。
※背理法にて証明可能。合成数XがX=A×Bとなる約数A・Bをもち、いずれもルートXより大きい場合、A×Bは√X＜Aかつ√X＜Bにより必ずX＜A×Bとなるため、X=ABであることと矛盾する。また３つ以上の約数を含む場合も、結合法則により最終的にA×Bの形に変形できるため同様。
