|
|
/*========================================================*/ ＜＜＜あゆしゃのＣ言語プログラミング＞＞＞ /*========================================================*/ 第５７１回 素因数分解のツール 発行 ２００５年６月８日（水曜日） 発行数 約２６００ {magclick} /*========================================================*/ はじめに （ 決り文句 ） /*========================================================*/ ・このメールマガジンは、主にまぐまぐさんから発行しています。 ・ジャンルは、マルチメディアのプログラム、Ｃ言語です。 ・横６０文字で作成し、インデントは大抵半角スペース４つです。 ・ここで扱うプログラムは、C言語と半光年以内のものです。 ・登録解除は、メルマガのホームページでお願いします。 ・過去ログはバックナンバー（下欄参照）を活用して下さい。 ・内容は私が感じたもので、最新の技術も、へたれもあります。 ・わかりやすさを優先させる為、たまに嘘があるかもしれません。 ・セキュリティ突破のため、暗号化された単語があります。 /*========================================================*/ ご挨拶 /*========================================================*/ こんにちは。あゆしゃです。 ヘルペスと診断されたあゆしゃ。 ヘルペスとは、神経に侵食するウイルスが原因による水疱瘡 （みずぼうそう）の１種で、水疱（すいほう＝みずぶくれ）と 神経痛を伴う病気。 ありがたいことに、お薬を飲むだけで完治するものです。 「バトルレックス」というすごい名前のお薬をいただきました。 高価なお薬らしいです。 １回２錠１日３回６日分で３６錠、約７０００円。 （診察料を含むので、６０００円かも） １錠あたり１９４円。 これが３割負担分なので、元の値段は１粒で６４０円。 総額２３０４０円！ 高いですねー、さすがバトルレックス。 {magclick} /*========================================================*/ 今回のお題 ＜＜ 素因数分解のツール ＞＞ /*========================================================*/ さて今回は少し話題を変えて、素因数分解のプログラムについて お話します。 ６００桁の数字の素因数分解に成功すると、２０００万円の 懸賞金がもらえます。 http://www.rsasecurity.com/rsalabs/node.asp?id=2093 素因数分解とは、そんなに難しいのでしょうか？ /*========================================================*/ さて、素因数分解のアルゴリズムを入れたソフトを作りました。 実行イメージ http://ayusya.hp.infoseek.co.jp/Image/prime_050605.jpg 実行ファイル http://ayusya.hp.infoseek.co.jp/Download/prime_050605_exe.zip プロジェクトファイル（MSVC++7.0） http://ayusya.hp.infoseek.co.jp/Download/prime_050605_prg.zip 型を６４ビットにしてあるので、結構大きな数字でも処理できま す。 処理時間も計測されます。 １０桁未満の数字では、時間は大抵０ですが。 ただし、１０桁を超える大きな数字を入れると、帰ってこなく なることがあるので、ほどほどにしてください。 /*========================================================*/ 321654987321 3 * 19 * 227 * 24859339 サンプル画像の計算結果では、８７２ｍｓでした。 /*========================================================*/ 11111111111 21649 * 513239 この計算に20ミリ秒かかりました。 /*========================================================*/ 2222222222222 2 * 53 * 79 * 265371653 私のパソコンでは、この計算に8.8秒かかりました。 まぁ、そんなもんです。 {magclick} /*========================================================*/ さいごに /*========================================================*/ {magclick} /*========================================================*/ 次回予告 /*========================================================*/ 次回は６月１０日（金曜日）に、第５７２回をお送りします。 お題は「素因数分解の高速化１」 ６００桁を実行するには、処理が重過ぎます。 お楽しみに！ /*========================================================*/ 最後の決り文句 /*========================================================*/ このメールマガジンは、まぐまぐさんから発行しています。 このメールマガジンを解除したい場合は、まぐまぐさんをご利用 ください。このメルマガのまぐまぐアイディーは最後にあります。 このメールマガジンには広告が挿入されていますか？ このメールマガジンの内容に文面の引用はありませんか？ めーらっくすの場合はめーらっくすの利用方に従ってください。 このメールマガジンの内容の、転用、流用、宣伝、リンク、 ただしくはバルトレックス なんて大歓迎です。 {magclick} /*========================================================*/ /*========================================================*/ 発行者 あゆしゃ ホームページ::あゆしゃの世界 http://ayusya.hp.infoseek.co.jp/ ご意見・ご感想・ご質問メール mailto:ayusya@flamenco.plala.or.jp まぐまぐ::アイディー 0000020674 まぐまぐ::登録と解除 http://www.mag2.com/m/0000020674.htm まぐまぐ::バックナンバー http://jazz.tegami.com/backnumber/frame.cgi?id=0000020674 めーらっくす::アイディー MM3E1AEE285AB4F めーらっくす::登録と解除 http://www.mailux.com/mm_dsp.php?mm_id=MM3E1AEE285AB4F めーらっくす::バックナンバー★最近のものならこちらが便利★ http://www.mailux.com/mm_bno_list.php?mm_id=MM3E1AEE285AB4F |