2004年度予選課題：SuperCon数探索問題 (©SuperCon実施委員会)

【問題】

素因数分解した時，（重複する分も含め）素数の延べ個数が ちょうど 12 個となる整数を SuperCon 数と定義します．

例） 3750000 = 2^4 * 3 * 5^7 （素数 2 が 4 個，3 が 1 個，5 が 7 個の合計 12 個）

与えられた整数 n（ただし 10,000,000 ≦ n ≦ 20,000,000）に対し， n から始めて 2004 番目の SuperCon 数 を求めるプログラムを作成しなさい． ただし，与えられた整数 n そのものが SuperCon 数の時は n を 1 番目の SuperCon 数とみなします．

【入出力】

入出力はともに文字列形式とします．バイナリ形式ではありませんので ご注意ください．
  • 標準入力から 整数 n を 1 個読み込みます．
  • 標準出力へ 2004 番目の SuperCon 数を出力します．

【参考】

n = 1 の時，2004 番目の SuperCon 数は 2105856 になります．

【プログラム作成上の注意】

  • 素数や SuperCon 数の表（の一部）を，あらかじめプログラム中に 埋め込むのは禁止します． プログラム中で計算によって表を作成するのは構いません．
  • 応募プログラムは VineLinux 2.6r4 (i386) + gcc 2.95.3（VineLinux 2.6r4 に バンドルされているバージョン）の環境でコンパイル/実行し性能を評価します． 
    http://www.ring.gr.jp/pub/linux/Vine/Vine-2.6/i386/
  • 上記の環境でコンパイル/実行できない応募プログラムは 評価の対象とならない可能性がありますので，あらかじめ ご了承下さい．
  • Cygwin や Services For UNIX には Windows 上で動作する gcc が含まれています（いずれも無料で入手できます）． ただし，これらのコンパイラを使用して作成した応募プログラムが， 評価環境で実際にコンパイル/実行できることを保証するもの ではありませんので注意してください． 
    http://www.cygwin.com/
http://www.microsoft.com/japan/windows/sfu/
  • 応募受理確認の際に，応募プログラムが評価環境において コンパイルできたかどうかをあわせて回答いたします． 応募プログラムが評価環境でコンパイルできるかどうか 確かめたい場合，応募締め切りに余裕を持って応募する ようにしてください．

【添付のレポートについて】

プログラム中の主要アルゴリズムのアイデアを説明するレポートを添 付してください．素因数分解などについては既存のアルゴリズムを調べて 利用しても構いませんが，その場合は利用したアルゴリズムについて レポート中できちんと説明してください． なお，添付ファイルの形式は，
    　
  • テキストファイル 　
  • PDF（OpenOffice 形式の文書を PDF に変換したものでも構いません）
  • MS Word
のいずれかとしてください．

【審査方法と審査基準について】

  • 提出されたプログラムは主催者側で用意した計算機上で実行されます．
  • 実行開始から 3 分が経過しても計算が終了しない場合は，そこで実行を打ち切ります．
  • 主催者側で用意したすべての入力に対して正解を出力したプログラムの内，実行時間の 短いほうから 10 チームを予選通過とします．
  • ただし，実行時間について 1〜2 秒程度の差しかみられなかった場合は 実行時間については同等であるとみなし，それらについてはレポートに より順位を決定します．
  • 万一，正解プログラムを提出したチーム数が 10 に満たなかった場合は 提出されたレポートをもとに残りのチームを決定します．

【予選問題に対する解答方法】

応募要項のページを参照してください． なお，予選問題に対する解答をもって参加申し込みとさせていただきます．

また，予選問題の内容に関する質問とその回答は，次のページで公開させて いただきますので、あらかじめご了承ください．
++ http://www.gsic.titech.ac.jp/supercon/supercon2004/q&a.html ++