|
|
/*========================================================*/ ＜＜＜あゆしゃのＣ言語プログラミング＞＞＞ /*========================================================*/ 第５７４回 素数判定処理 発行 ２００５年６月１５日（水曜日） 発行数 約２６００ {magclick} /*========================================================*/ はじめに （ 決り文句 ） /*========================================================*/ ・このメールマガジンは、主にまぐまぐさんから発行しています。 ・ジャンルは、マルチメディアのプログラム、Ｃ言語です。 ・横６０文字で作成し、インデントは大抵半角スペース４つです。 ・ここで扱うプログラムは、C言語と半光年以内のものです。 ・登録解除は、メルマガのホームページでお願いします。 ・過去ログはバックナンバー（下欄参照）を活用して下さい。 ・内容は私が感じたもので、最新の技術も、へたれもあります。 ・わかりやすさを優先させる為、たまに嘘があるかもしれません。 ・セキュリティ突破のため、暗号化された単語があります。 /*========================================================*/ ご挨拶 /*========================================================*/ こんにちは。あゆしゃです。 現在、攻殻がアニメ放送中です。 その少し前に、ガラスの仮面がアニメ放送中です。 あゆしゃ、攻殻、大好きです。 あゆしゃ、ガラスの仮面、大好きです。 野球で３０分延長しても、この２つのアニメはかぶさらないよう に、始めから３０分の空きを入れて放送されています。 局の枠を超えてこの仕組みを作った紫のバラの人に、 感謝しなければいけません。 それにしても、仮面を装備するマヤ、怖いです。。 {magclick} /*========================================================*/ 今回のお題 ＜＜ 素数判定処理 ＞＞ /*========================================================*/ さて今回は少し話題を変えて、素因数分解のプログラムについて お話します。 ６００桁の数字の素因数分解に成功すると、２０００万円の 懸賞金がもらえます。 http://www.rsasecurity.com/rsalabs/node.asp?id=2093 素因数分解とは、そんなに難しいのでしょうか？ /*========================================================*/ 今回は、素数を判定する処理を作ります。 int chk_prime( int d ) { if( ( d & 1 ) == 0 ) return 0; // 偶数は素数ではない int a = 3; while( a < d ) { if( ( d % a ) == 0 ) return 0; // 素数ではない a += 2; } return 1; // 素数です } こんな感じでしょうか。 基本的には素因数分解の処理と同じです。 偶数である場合は２の倍数なので、除外します。 ループは、チェックする素数（と思われる数）が、指定された数 よりも小さい間ループします。 素数で割り切れた場合、その数は素数ではありません。 加算処理は、とりあえず＋２でよいでしょう。 マイナスの値を指定された場合は無効ですがまぁいいでしょう。 {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 |