はじめに

アニメ「すべてがFになる」を見て「すべてがFになる(計算機工学版)」を作ったが、これを使って
高速な素数判定の前処理が可能です。ハードウェア向きのアルゴリズムですが、ソフトウェアでも高速化できるかも。
最近はFPGAつきのCPUがあるので、役に立つことがあると思ったので、投稿します。
素数判定の前処理の論文もあったようです。

2016年7月11日追記
証明については2014年度から高校の数学Aの整数の性質で学ぶ合同式を使えば簡単にできます
それだと「すべてがFになる」の意味がわからなくなってしまいますが

「すべてがFになる」とは

推理作家森博嗣のミステリー小説。第1回メフィスト賞（1996年）受賞作。S&Mシリーズの第1巻。
登場人物の真賀田四季は、「人類のうちで最も神に近い」と言われる天才プログラマー。29歳。
情報工学、特に仮想現実、人工知能の領域で研究実績がある他、多様な分野の話題について有益な意見を出せる知能を持つ。
などなど、詳しくはWikipediaの真賀田四季を参照。

「すべてがFになる(計算機工学版)」とは

原作とは、全然違うが、イメージがぴったりの話ができてしまったので、ついつい残してしまったもの。

7で割った余りの説明

「7は特別な数字、数字の中で7だけが孤独」は、アニメの第１話で真賀田四季が言ったセリフだが、ここでは

ある数を7で割った余りは、ある数を8進数で表すと
abcの場合、a+b+cを7で割った余りと同じになる

7が特別な数字だから、そうなるのだ。みたいな。
これを一般化してハードウェアで実装すると

15で割った余りの証明

ある数を15(←16進数でF)で割った余りは、ある数の
16進数の各桁の総和を15で割った余りと同じになる

すべてがFになる の呪文によって証明される。

\begin{align}
16^m-1 &= 15×16^{m-1} + 16^{m-1} - 1\\
 &= 15×16^{m-1}+15×16^{m-2}+16^{m-2} - 1\\
 &= 15×16^{m-1}+15×16^{m-2}+15×16^{m-3}+16^{m-3} - 1\\
 &= 15×16^{m-1}+15×16^{m-2}+15×16^{m-3}+15×16^{m-4}+…+16-1 \\
 &= 15×16^{m-1}+15×16^{m-2}+15×16^{m-3}+15×16^{m-4}+…+15 \\
 &= 15×(16^{m-1}+16^{m-2}+16^{m-3}+16^{m-4}+…+1)
\end{align}

高速な素数判定の前処理のアルゴリズム

15は、3×5なので15で割った余りを計算できれば、3と5の倍数であるかを判定できる。アルゴリズムは7で割ったあまりのハードウェア実装と同じ。これである巨大な数字が3,5,7の倍数であるかどうかを、高速に判定可能で、ある数が3の倍数である確率は33%なので、これだけでも、かなり高速になるのではと思います。
同じ原理で、もう少し大きな素数も、できると思いますが、性能とコストのトレードオフで選択するといいように思います。

2016年7月11日追記
ランダムに生成された数字を素数判定する目的であれば、ほんの少し性能を向上させてくれるかもしれない。
GNUのGMPというライブラリでmpz_nextprime()という関数は3、5、7のような小さい素数で割り切れるかをテストしている。
しかし与えられた数よりも大きい素数を探すのに毎回、3、5、7で割れるかを判定しているわけではなく、前回の結果を記録しておいて、 増分を計算して判定するため、この方法の高速性は活かされないことが判明した。

2020年4月4日追記
上記アルゴリズムをC言語のプログラムにしたものを記載していましたがプログラムにバグがあったので削除しました。