SuperCon数探索アルゴリズム

　●今回のプログラムでは、以下の値をあらかじめ算出しました。

　１．n = 20,000,000 の時の 2,004 番目の SuperCon 数は、21,561,984。 　２．21,561,984 の平方根はおよそ 4,643。 　３．21,561,984 を 2の11乗で割ると、およそ 10529。 　４．5の12乗は 244,140,625 で明らかに 20,000,000より大きい。

　●使用変数一覧 　　n 　　　　代入された初期値(10,000,000 ≦ n ≦ 20,000,000)

　　Prime配列 　　　　素数リストを格納する配列

　　ii 　　　　繰り返し処理のインデックスや、その他多目的用途

　　jj 　　　　繰り返し処理のインデックスや、その他多目的用途

　　c 　　　　リストアップした素数の個数

　　flag 　　　　SuperCon数を直接求めるためのフラグ。 　　　　フラグの中身は「素数リスト内の何番目か」

　　sortarray配列 求めたSuperCon数を格納する。 　　　　小さい順に格納されていくわけではないので、 　　　　最終的にはこの中身をソートする。

　　cnt sortarrayに格納したSuperCon数の個数

　●アルゴリズム説明

　　★素因数分解

　　・上限値(21,561,984)を 2の11乗 で割ったときのあまりは およそ10529なので、 　　　10529までの素数リストを作成する。

　　・変数 ii が素数かどうかは ii が ii 未満の整数で割り切れるかどうかを 　　　2まで繰り返し、割り切れるものが合った場合は、素数で無いとして 　　　ループを抜ける。ループの最後まで言っても割り切れる数が無かったら 　　　その数は素数と判断する。

　　・数学的に考えると、√n以上の整数で割っても割り切れることは無いので、 　　　√n 未満の整数で割り切れるかどうかを 2まで繰り返すことにする。

　　・素数リストの一番最初に代入されている Prime[0] = 0 は、 　　　素数リストを作成するために代入しているのではなく、 　　　後に行う SuperCon数探索の時に プログラムを組みやすくするための 　　　ダミーの役割で使っています。

　　★SuperCon数探索

　　・「12個の素数の掛け算の答えは常にSuperCon数である」ということを利用して、 　　　素数リストを利用して 22222222222*2 = 4,096 から 順々に 　　　12個の素数の掛け算、つまりSuperCon数をリストアップしていく。

　　・素数同士の掛け算は、必ず「左側の項は右側の項より小さい」ことになります。

　　　【例】223 = 232 = 322 と、結果が同じになるパターンができるので、 　　　　　　速度を求める上で、全パターンを計算するのは好ましくないので、 　　　　　　「左側の項は右側の項より小さい」原則を決めて、 　　　　　　重複するパターンのうち１つのみ計算することにしました。

　　・上限値(21,561,984)を超えた場合、「項の繰り上がり」をする。

　　　【例1】22...2119767 の計算結果が上限値(21,561,984)を超えたとき、 　　　　　　 22*...2119769 は明らかに上限値を超えている。 　　　　　 　これ以上 第12項の素数を大きくしても無駄ということになるので、 　　　　　 　第11項の素数を1つ大きくし、「左側の項は右側の項より小さい」から、 　　　　　 　22*...213*13 が次にチェックするSuperCon数になる。

　　　【例2】22...21313 がの計算結果が上限値(21,561,984)を超えたとき、 　　　　　　 22*...21313 は明らかに上限値を超えている。また、 　　　　　　 22*...21717 も明らかに上限値を超えている。 　　　　　　 これ以上 第11,12項の素数を大きくしても無駄ということになるので、 　　　　　　 第10項の素数を1つ大きくし、「左側の項は右側の項より小さい」から、 　　　　　　 22*...33*3 が次にチェックするSuperCon数になる。

　　・求めたSuperCon数のうち、以下の条件のものはリストに格納しない。

　　　１．入力された数 ( n ) 未満の SuperCon数 　　　２．上限値(21,561,984) より大きい SuperCon 数

　　★ソート

　　・SuperCon数の一覧が格納された配列は小さい順に並んでいるわけではないので、 　　　ソートする必要があります。

　　・今回は、stdlib.h 内で定義されている qsort()関数を使って、 　　　クイックソートを行いました。

　●その他の方法

　・試作型として、n から順々に素数リストで割っていく方法のプログラムも 　　考えましたが、答えを求めるのに平均 14秒 ほどかかったので、 　　今回は割るのではなく、逆に、掛ける方法でプログラムを組みました。

、●実行環境 　　・n=10,000,000 の時、答えは 11,635,712（実行時間：121ミリ秒） 　　・n=15,000,000 の時、答えは 16,592,000（実行時間：110ミリ秒） 　　・n=20,000,000 の時、答えは 21,561,984（実行時間： 70ミリ秒）

　　・OS : Windows Xp Professional SP1 　　・CPU : Mobile Athron XP 1600+ 　　・Memory : DDR SD-RAM 352MB 　　・Compiler : Microsoft Visual C++ .NET 2002