素数-prime number
本日素数を求めるプログラムについて考えました。
なかなかすんなりいかないな…がっかり
何て思わず一歩ずつ前進していきましょう。
それでは素数(prime number)について
1.素数は1と素の数でしか割れない数字
2.また2以降の素数は奇数
この点を少し抑えてプログラムを組んでみます。
配列prime[10]に素数を格納するプログラムです。
int main (void) { int i, n, c, prime[10]; /*配列の先頭に"2"を挿入しておきましょう*/ prime[0] = 2; printf("%d\n",prime[0]); c = 1; for( n = 3; c < 10; n += 2 ){ for( i = 3; i < n; i += 2 ){ //※1 if( n % i == 0 ){ break; } } //※2 if( n == i ){ prime[c] = n; printf("%d\n",prime[c]); c++; } } return 0; }
まず※1のif文について
これはnがiで割りきれることを示しています。
iは3,5,7,…と続いていきます。
よって途中で割りきれる数字が出てしまったら、
それは素数ではなくなりますよね。
次に※2のif文について
これは最後まで割り切れなかった数字です。
ようは n == i でその数字でしか割れていないわけです。
これは素数になります。
for文内の n += 2 は、奇数を表しています。
今回は
柴田望洋+辻亮介 著
「新版C言語によるアルゴリズムとデータ構造」
- 作者: 柴田望洋,辻亮介
- 出版社/メーカー: ソフトバンククリエイティブ
- 発売日: 2005/08/27
- メディア: 大型本
- 購入: 4人 クリック: 14回
- この商品を含むブログ (23件) を見る
いやー正直そのままといってもいい…
でも自分なりに整理し、噛み砕いて見ました。
これを見たことにより一人でも多くの方がこの本を読んでくれることを願っています。