素数、文字列探索の基礎

素数に関するアルゴリズム

これまでは、素数研究が社会に直接関係することはあまりありませんでした。ところが、電子メールなどの暗号化が必要になりました。その暗号鍵、復号鍵では、「非常に大きいを素因数分解する計算には非常に時間がかかる」ことをベースにしています（→参考：「公開鍵暗号方式の原理」）。そのため、素数に関する関心が高まっているのです。

２，３，５，７，１１，１３，１７，…など、１と自分自身でしか割り切れない数を素数といいます。１２＝４×３や、１８＝２×９のように、素数ではない数のことを合成数といい、２、３、４、９など、合成数を割り切れる数を約数といいます。そして、２や３など約数自体が素数であるとき、その約数を素因数といいます。

素数を扱うアルゴリズムは、大きく３つに区分されます。

素数判定

与えられた数ｎが素数であるかどうかを判定するアルゴリズムです。
ｎ＝１２のとき、「約数４が見つかったので１２は素数ではない」というように、一つの約数を見つければよいことになります。

素因数分解

１２＝２×２×３、１８＝２×３×３のように、合成数を構成するすべての素因数とその個数を列挙するアルゴリズムです。素因数分解のほうが複雑になります。一般的には、素数判定のアルゴリズムを発展させて、素因数分解に用いています。

最大公約数

二つの数が与えられたとき、共通の約数のうち、最大のものを最大公約数といいます。例えば、１２と１８の最大公約数は６になります。
素数判定や素因数分解の計算量が非常に大きいのに比較して、最大公約数は少ない計算量で求められます。それで、素数判定や素因数分解を高速化するアルゴリズムでは、最大公約数のアルゴリズムを利用することが多いのです。

「割り切れる」とは剰余が０のことですので、素数であるかどうかは剰余を求める計算が重要になります。
　プログラムでは、ａをｂで割ったときの剰余は、
　　ａ mod ｂ　（Ｃ言語）
　　ａ % ｂ　　（Javascript）
で求められます。

ユークリッドの互除法

最大公約数（ＧＣＤ：Greatest Common Divisor）とは、２つの正整数ａとｂを素因数分解してときの共通項です。例えば
　　　ａ＝９２４（＝２×２×３×７×１１）
　　　ｂ＝３６０（＝２×２×２×３×３×５）
の最大公約数Ｇは
　　　Ｇ＝２×２×３＝１２
になります。

なお、最小公倍数（ＬＣＭ：Least Common Multiple）は、ａとｂでありきれる最小の整数のことです。
　　　ａ＝Ｇ×（７×１１）
　　　ｂ＝Ｇ×（２×３×５）
なので、最小公倍数Ｌは、
　　　Ｌ＝Ｇ×（７×１１）×（２×３×５）
となります。すなわち、
　　　Ｌ＝ａ×ｂ／Ｇ＝９２４×３６０／１２＝２７７２０
で計算できます。

ユークリッドの互除法は、最大公約数を計算する効率的なアルゴリズムです。

アルゴリズム

正整数ａ、ｂ（ａ＞ｂ）の最大公約数を求める手順を示します。
　　ア　ａをｂで割った剰余をｒとする。
　　イ　ｒが０ならばｂが最大公約数である。
　　ウ　ｒが０でないならば、ａ←ｂ、ｒ←ｂとして、アへ戻る。

プログラム

　　function euclid(a, b) {
　　　　r = a % b;　　　　/* ｒはａ／ｂの剰余 Ｃ言語なら a mod b と記述 */
　　　　while (r > 0) {
　　　　　　a = b;
　　　　　　b = r;
　　　　　　r = a % b;
　　　　}
　　　　return b;
　　}

数値例

（ａ＝９２４、ｂ＝３６０）
　　　ａ　　　ｂ　　　ｒ
　　９２４　３６０　２０４（＝９２４－２×３６０）
　　３６０　２０４　１５８（＝３６０－１×２０４）
　　２０４　１５８　　４８（＝２０４－１×１５８）
　　１５８　　４８　　１２（＝１５８－３×４８）
　　　４８　　１２　　　０（＝４８－４×１２）
　　　　　　　 └─→最小公倍数＝１２

素数判別

単純なプログラム

与えた数ｎが素数であるときは１、約数のときは０を戻す、単純なプログラムを示します。
ｉを２からｎ－１まで変化させ、そのなかでｎを割り切れたら０、どれでも割り切れなかったら１を戻します。
　　function prime(n) {
　　　　for(i=2; i<=n-1; i++) {
　　　　　　if ((n % i) == 0) return 0;
　　　　}
　　　　return 1;
　　} これではあまりにも非効率です。例えば、

• ｎが２つの数の積になるのであれば、小さいほうの数は、√ｎの以下になります。ｉの上限値を√ｎにすべきです。
• ２で割れないのであれば、それ以上の偶数で割り切れるはｓずがありません。ｉが３以上の場合はｉが奇数のときだけチェックすればよいことになります。

それらを考慮すると、次のようになります。
　　function prime(n) {
　　　　if ((n % 2) == 0) return 0;
　　　　for(i=3; i<=Math.sqrt(n); i++) {
　　　　　　if ((n % i) == 0) return 0;
　　　　}
　　　　return 1;
　　}

エラトステネスのふるい

上と同様に考えて、ｎがある数で割りきれないときは、その倍数のチェックをする必要がありません。それで、table[i] という表を用意しておき、ｉで割り切れたときは、ｉの倍数ｋについて、table[k] を０にします。このようにして、素数を求めていくのです。
　　function eratosthenes(n) {
　　　　table = new Array(101);
　　　　　　　　　　　　　/* 初期設定：とりあえず２と奇数は素数だと仮定しておく */
　　　　for (i=0; i<= n; i++) table[i] = 0;
　　　　table[2] = 1;
　　　　for (i= 3; i<=n; i=i+2) table[i] = 1;
　　　　　　　　　　　　　/* ３以上、ｎの平方根以下の奇数について */
　　　　for (i=3; i<=Math.sqrt(n); i=i+2){
　　　　　　if (table[i] == 0) continue;
　　　　　　　　　　　　　/* 既に倍数になっているならチェックしない */
　　　　　　for (j=i+i; j<=n; j=j+i) table[j] = 0;
　　　　　　　　　　　　　/* ｊ＝２×ｉ、３×ｉ、…は倍数であるとする */
　　　　　　　　　　　　　/* このようにして、ふるいにかけられて、素数が減少する */
　　　　}
　　　　return table[n];
　　}
エラトステネスのふるいでは剰余の計算が不要です。その観点からも効率的になります。

文字列の検索

文字列検索とは、テキストの文字列内に、パターンの文字列と一致する部分文字列が存在するかどうかを調べ、存在したならば、その位置を求めるという操作です。
　デジタルデータが急激に増大しています。それらから有用なデータを、容易に入手することが重要になります。データが事前に体系づけて保管されていない場合が多いですし、体系づけられていたとしたとしても、他の切り口で探索することが必要な場合もあります。それに対処するには、検索エンジンのように、与えられた文字列を含むデータを全文探索することが必要になります。
　効率的な探索を行うために、多様な方法がとられていますが、最も基本的な方法が、文字列探索です。
例えば、
　　　テキストの文字列が「ｄａｂｄａｂｃａｂｃｂａ」
　　　パターンの文字列が「ａｂｃｂ」
の場合
　　　　　　　　　　　　　　　　　　　１１
　　　　　　　　　０１２３４５６７８９０１
　　　テキスト：　ｄａｂｄａｂｃａｂｃｂａ
　　　パターン：　　　　　　　　ａｂｃｂ
となるので７を戻し、パターンが「ａｂｃｘ」の場合は、テキストに一致する部分文字列が存在しないので、－１を戻す関数を考えます。

以下、テキストは配列ｔ、パターンは配列ｐに入っており、テキストの文字列長さをｎ、パターンの文字列長さをｍとします。上の例では、
　　　t[0]="d", t[1]="a", … , t[11]="a"　　n=12
　　　p[0]="a", p[1]="b", … , p[3]="b" 　　m=4
となります。（ｔ、ｐは０から始まり、ｎ、ｍは個数であることに注意）
　なお、プログラムでは、これらの値はグローバル変数として定義されているものとします。

プログラム

ア　function simple() {
イ　　　var i, j;
ウ　　　for (i=0; i<=n-m; i++) {
エ　　　　　for (j= 0; j<m; j++) {
オ　　　　　　　if (t[i+j] != p[j]) break;
カ　　　　　}
キ　　　　　if (j == m) return i;
ク　　　}
ケ　　　return -1;
コ　}

アルゴリズム

ｔ[ｉ]以降とｐが一致しているかを調べるには、ｐのｊ番目の文字ｐ[ｊ]とｔ[ｉ＋ｊ]を比較することが基本になります（オでの比較）。
下表では、ｉ＝３、ｊ＝２（ｉ＋ｊ＝５）のとき、ｔ[５]＝ｂとｐ[２]＝ｃを比較しています。
　　　　　　ｉ　i+j 　n-m　ｎ
　　　　　　↓　↓　　↓　　　↓
　　　０１２３４５６７８９101112
ｔ：　ｄａｂｄａｂｃａｂｃｂａ
ｐ：　　　　ａｂｃｂ
　　　　　　　　↑
　　　　　　　　ｊ

一致していないならば、それ以上この位置で比較する必要はないので、ｐ全体を右に一つ移動させ（ｉに１を加えて）ｐの先頭から（ｊ＝０として）比較します（オのbreak）。
一致していれば（図では一致していないが）、ｊに１を加えて、ｔ[６]＝ｃとｐ[３]＝ｂと比較します。

キで ｊ＝ｍ のときに打ち切っているのは、パターンのすべての文字が一致したときは、ｊ＝ｍ－１であり、それがｊ＝ｍになったときにエ～カのループから出てキへ行くからです。

ウで ｉ≦ｎ－ｍ（１２－４＝８）としたのは、ｉ＝９になると、ｐが最期までいったとき（ｊ＝３になったとき）に、ｉ＋ｊ＝１２となり、オで ｔ[ｉ＋ｊ] がｔの配列上限を超えてしまう（オーバーフローする）からです。

トレース

ｉはｔの要素番号、ｊは比較するｐの要素番号。ｉ＋ｊが比較位置

ｉ　ｊ i+j　０１２３４５６７８９０11
　　　　　　ｄａｂｄａｂｃａｂｃｂａ
０　０　０　ａｂｃｂ　　赤字は不一致を示す→ｉに１を加えｊを０にする
１　０　１　　ａｂｃｂ　青字は一致を示す→ｊに１を加える
１　１　２　　ｂａｃｂ
１　１　３　　ａｂｃｂ
２　０　２　　　ａｂｃｂ
３　０　３　　　　ａｂｃｂ
４　０　４　　　　　ａｂｃｂ
４　１　５　　　　　ａｂｃｂ
４　２　６　　　　　ａｂｃｂ
４　３　７　　　　　ａｂｃｂ
５　０　５　　　　　　ａｂｃｂ
５　１　６　　　　　　　ａｂｃｂ
７　０　７　　　　　　　　ａｂｃｂ
７　１　８　　　　　　　　ａｂｃｂ
７　２　９　　　　　　　　ａｂｃｂ
７　３　10　　　　　　　　ａｂｃｂ　　すべて一致
└　一致位置（戻す値）

計算量

ウでｉをｎ－ｍ回行い、エでｊをｍ回行っています。もし、一致する部分文字列が存在しなかったときは、オがすべてのｉ、ｊの組合せで行うことになり、その比較回数は、(ｎ－ｍ)×ｍ回になります。ｎに対してｍが小さいなら、約ｎ×ｍ回の比較になります。それで、この方法の計算量オーダーは Ｏ(ｎ×ｍ) になります。