素数判定法
１．2821109907457が素数かどうか知りたいのですが、どのような方法をとったらいいでしょうか？その数の平方根までの素数で割れなければ素数。√2821109907457≒1679616なので、1679616までの素数で割り切れなければ素数。1679616までの素数を列挙するのも手間なので、例えば1679616までの奇数で割れるかを調べれば良い。もう少し工夫すると、奇数の中でも6n+3の形は3の倍数で素数ではないので、これを除くと素数は、6n-1、もしくは、6n+1のいずれかの形。だから、6n-1、もしくは、6n+1で割ると効率が良い。
２．手で計算するのは大変なので、1679616まで6n-1、もしくは、6n+1で割った余りを計算し、もし割り切れたら、その数を表示するプログラム（割り切れる数が１つも無かったら、素数と判定する）を書くと、瞬時に、353、1697、599041(=353x1697)、で割り切れ、素数でないことが分かる。実際に、3～1679616までの、6n-1、もしくは、6n+1の形の奇数（全部で5599871個）で割るのに掛かる合計時間は、たったの0.007秒程度。桁数が多いので、Ｃ言語だと、long long intの変数、を使う必要がある。