|
|
/*========================================================*/ ＜＜＜あゆしゃのＣ言語プログラミング＞＞＞ /*========================================================*/ 第５７７回 加算表作成処理 発行 ２００５年６月２２日（水曜日） 発行数 約２６００ {magclick} /*========================================================*/ はじめに （ 決り文句 ） /*========================================================*/ ・このメールマガジンは、主にまぐまぐさんから発行しています。 ・ジャンルは、マルチメディアのプログラム、Ｃ言語です。 ・横６０文字で作成し、インデントは大抵半角スペース４つです。 ・ここで扱うプログラムは、C言語と半光年以内のものです。 ・登録解除は、メルマガのホームページでお願いします。 ・過去ログはバックナンバー（下欄参照）を活用して下さい。 ・内容は私が感じたもので、最新の技術も、へたれもあります。 ・わかりやすさを優先させる為、たまに嘘があるかもしれません。 ・セキュリティ突破のため、暗号化された単語があります。 /*========================================================*/ ご挨拶 /*========================================================*/ こんにちは。あゆしゃです。 実を言うと最近、ゲームをしていないあゆしゃ。 意外かもしれませんが、私はそれほどゲームが好きなわけでは ありません。 なので、義務感を持ってゲームをクリアしなければいけない、 ということはしません。 スターフォックス、メトロイド、半熟英雄と、期待しつつも ちょっとやって「つまらん」とさじを投げてしまい、 非常に暇な日々を送っています。 それが原因でしょうか、第５７５号の配信時間を間違えて 「即時配信」にしてしまいました。 非常事態です。 {magclick} /*========================================================*/ 今回のお題 ＜＜ 加算表作成処理 ＞＞ /*========================================================*/ さて現在は少し話題を変えて、素因数分解のプログラムについて お話します。 ６００桁の数字の素因数分解に成功すると、２０００万円の 懸賞金がもらえます。 http://www.rsasecurity.com/rsalabs/node.asp?id=2093 素因数分解とは、そんなに難しいのでしょうか？ /*========================================================*/ 前回、○×素数表を作成しました。 それを応用して、素因数分解の処理を高速化するための加算表を 作る処理を作成します。 // 呼び出し元 const char* name = "c35"; CString filename = make_prime_add_list( name, 5 ); ShellExecute( m_hWnd, "open", filename, NULL, NULL, SW_SHOW ); // 関数本体 #define EN "\n" CString make_prime_add_list( const char* name, int maxnum ) { CString ret; if( maxnum < 3 ) return ret; FILE* fp = NULL; int* data = NULL; do { // ファイルオープン char filename[ MAX_PATH ]; sprintf( filename, "prime_add_list_%s.h", name ); fp = fopen( filename, "wt" ); if( ! fp ) break; ret = filename; // maxnumまでのすべての素数の最小公倍数 int minimax = 3; for( int d = 5; d <= maxnum; d += 2 ) { if( chk_prime( d ) ) { minimax *= d; } } // ○×表のデータサイズの決定 int datasize = minimax + 10; // データ領域を取得 data = new int[ datasize ]; if( ! data ) break; memset( data, 0, sizeof( int ) * datasize ); // ○×データ作成 int a = 3; int m = 1; do { // この前までのすべての素数の倍数ではない場合 if( data[ a ] == 0 ) { // この素数の倍数を除外する int a2 = a * 3; while( a2 < datasize ) { data[ a2 ] |= m; a2 += a * 2; } m <<= 1; } // 次の素数 do { a += 2; } while( ! chk_prime( a ) ); } while( a <= maxnum ); // 最小公倍数の位置にある○×状態 m--; ASSERT( data[ minimax ] == m ); // データ出力開始 fprintf( fp, "const int %s[] = {" EN, name ); // 最後のデータを出力 fprintf( fp, "0};" EN ); } while( ! fp ); // 後片付け if( fp ) fclose( fp ); if( data ) delete[] data; return ret; } まずは、がらのみ。 ファイルを開き、最小公倍数を求め、必要なデータ領域を用意し ○×素数表をデータ上に作成します。 何の倍数であるかを識別できるように、素数ごとに対応する ビット単位で、表を埋めていきます。 ASSERTにあるように、データを作成した後の最小公倍数の 位置には、指定した素数を含むすべての素数の倍数である ことを示すように、すべてのビットが立っている、はずです。 この部分が加算表の折り返し地点になる、はずです。 次回、データ出力部分の内容を作成します。 /*========================================================*/ 素数同士の最小公倍数は、必ずお互いをかけた数になります。 データ領域は偶数部分が必要ありませんが、まぁいいでしょう。 {magclick} /*========================================================*/ さいごに /*========================================================*/ 終了処理については、私が良く使うブレイク方式です。 Cマガになかったのが残念ですが、tryに近いかな？ {magclick} /*========================================================*/ 次回予告 /*========================================================*/ 次回は６月２４日（金曜日）に、第５７８回をお送りします。 お題は「加算表作成処理２」 加算表のCソースを出力する部分を作成します。 お楽しみに！ /*========================================================*/ 最後の決り文句 /*========================================================*/ このメールマガジンは、まぐまぐさんから発行しています。 このメールマガジンを解除したい場合は、まぐまぐさんをご利用 ください。このメルマガのまぐまぐアイディーは最後にあります。 このメールマガジンには広告が挿入されていますか？ このメールマガジンの内容に文面の引用はありませんか？ めーらっくすの場合はめーらっくすの利用方に従ってください。 このメールマガジンの内容の、転用、流用、宣伝、リンク、 ヘルペス完治 なんて大歓迎です。 {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 |