配列を使用して素数を求める

Question

実現したいこと

素数を配列を使って求めたい。
また表示を10の桁ごとに数え、その素数の数だけを’＊’で表示させたい。
配列を使用しない場合で素数を求めるプログラムを書くことができたのですが、配列を使うとなると分からなくなってしまいました。

該当のソースコード

ソースコード
int main(void) {
	int i, j;
	int ture;
	for (i = 2;i <= 1000;++i) {
		ture = 0;
		for (j = 2;j < i;++j) {
			if (i % j == 0) {
				ture = 1;
				break;
			}
		}
		if (ture == 0) {
			printf("%d\n",i);
		}
	}
	return 0;
}

### 試したこと
ここに問題に対して試したことを記載してください。

### 補足情報（FW/ツールのバージョンなど）

ここにより詳細な情報を記載してください。

Comments

[SaitoAtsushi]

配列を使うというのはどのように使うことを想定していますか？
配列をどのように使えるかわからないという質問なのですか？

[jimbe]

「該当のソースコード」にはソースコードだけを書いてください。

[otn]

> 配列を使うとなると分からなくなってしまいました。

質問ポイントが不明です。
１．Cにおける（あるいはプログラミングにおける）配列とは一体何なのかが理解できてない
２．配列は理解できていて、配列を使ったプログラムは書けるが、「素数を配列を使って求めろ」と言われて、素数と配列の関係が分からない
⇒ この場合は「エラトステネスの篩」を調べましょう
３．素数を求めるときに配列をどのように使うかまでは分かっているが、コードが書けない
⇒ この場合は配列をどのように使おうと思っているかを書きましょう
などなど。

[nanashi_09]

配列というものがどのようなものか分かっていないため、配列を使用して書くことができない。

[otn]

> 配列というものがどのようなものか分かっていないため、配列を使用して書くことができない。
基本的なことを学ぶのはQAサイトでは難しいです。
配列とはどういう物かは、多くの人はプログラミング入門書を読むなどで自力で理解します。
あなたが理解できないというのは、どこかで何らかの思い違いなどがあるのだと思いますが、それが何か分からないので、乗り越えさせようが無いわけです。

誰か先生がいるなら相談する。基本的なことが自力で理解できない時は対面で教わるのが一番です）。対面であれば、あなたの理解状況が把握できます。
先生がいない場合は、入門書などで勉強しているのでしょうが、理解できるまで繰り返し読むとかしかないですね。

Answer 1

10ごとに*を表示するだけなら、次のプログラムで実現できます。
「配列を使う」の意味がちがうかも知れませんけど。
出来るだけ簡単なことからやってみると、どんどん理解が深まりますよ！

#include <stdio.h>
#include <string.h>

int main(void) {
int i, j;
int ture;
int kosu=0;
char hosi[32];

memset(hosi,'*',10);

for (i = 2;i <= 1000;++i) {
	ture = 0;
	for (j = 2;j < i;++j) {
		if (i % j == 0) {
			ture = 1;
			break;
		}
	}
	if (ture == 0) {

/////// printf("%d\n",i);
kosu++;
}

	if ( i%10==0 ) {
		printf("%3d～%3d: %.*s\n",i-9,i,kosu,hosi);
		kosu=0;
	}
}

return 0;

}

Answer 2

配列の使い方はいろいろ考えられますが，C99 で導入された「ブーリアン（boolean）型」の配列を用いた記述例を下記に示します。

• アルゴリズムは エラトステネスの篩 を参考にしました。

• ブーリアン型配列 is_prime[i] の値（true, false）に「i が素数か否か」の意味を持たせ，この配列の値が（ i = 1 〜 N で）正しくなるように計算していきます。

#include <stdio.h>
#include <stdbool.h>
#include <math.h>

#define N 1000

int main(void)
{
    bool is_prime[N + 1];  // is_prime[0] is not used
    int m = sqrt(N + 0.5);  // round down to integer
    int i, j;

    is_prime[1] = false;

    for (i = 2; i <= N; i++)
        is_prime[i] = true;

    for (i = 2; i <= m; i++) {
        if (!is_prime[i])
            continue;
        for (j = i * i; j <= N; j += i)
            is_prime[j] = false;
    }

    for (i = 1; i <= N; i++) {
        if (is_prime[i])
            printf(" %4d", i);
        if (i % 10 == 9 || i == N)
            printf("\n");
    }

    return 0;
}

    2    3    5    7
   11   13   17   19
   23   29
   31   37
   41   43   47

  ...

  953
  967
  971  977
  983
  991  997

Answer 3

otn さんがコメントでも触れていらっしゃいましたが、まずは「エラトステネスのふるい」法を、とりあえず１から１００迄で良いので、自分の手で紙に書いて実践し、理解するところから始めることを強くおすすめします。

とは言え、その理解したアルゴリズムを、配列を使った C プログラムに、どのように落とし込めば良いのか、
また、「表示を10の桁ごとに数え、その素数の数だけを’＊’で表示」とはどういう意味なのか、
すでに、かなりの時間考えた末、厚い壁にぶち当たった感覚があるのではないかと思います。
（私も昔はそうでしたから）

そこで、昔使っていた C の記憶を掘り起こして(汗)、「自分だったらこうするかな」というサンプルを書き下ろしてみました。

#include <stdio.h>
#include <math.h> /* sqrt() */

#define MAX_PRIME 1000 /* 素数を調べたい上限 */
#define IS_PRIME 0 /* 素数である */
#define IS_NOT_PRIME ( !IS_PRIME ) /* 素数でない */

int main( void ) {
    int primes[ MAX_PRIME ] = { IS_PRIME }; /* まず配列の全ての要素が「素数である」と仮定する */
    int sqrt_max_prime = ( int )sqrt( ( float )MAX_PRIME ); /* 「エラトステネスのふるい」では全体の平方根より先を調べる必要が無いのでその停止値をあらかじめ求めておく */
    int step; /* ふるいにかけた回数（処理の本筋とは関係無いが「エラトステネスのふるい」の収束の速さを可視化するための変数） */
    int check_prime; /* ふるいにかける素数 */
    int i, j;

    primes[ 0 ] = primes[ 1 ] = IS_NOT_PRIME; /* 素数の定義により */

    step = 1;
    check_prime = 2; /* 最初のふるいは最初の素数を採用する */
    while ( check_prime < sqrt_max_prime ) {
        printf( "step %d, checking prime number = %d\n", step, check_prime );
        for ( i = check_prime + check_prime; i < MAX_PRIME; i += check_prime ) { /* ふるいの「次」以降は素数ではない */
            primes[ i ] = IS_NOT_PRIME;
            printf( "%d ", i );
        }
        printf( "\nis not prime\n\n" );

        check_prime += 1; /* 次のふるいを仮定する */
        while ( primes[ check_prime ] == IS_NOT_PRIME ) { /* すでに素数でないものは次のふるいに採用しない */
            check_prime += 1;
        }
        step += 1;
    }

    /* 素数を表示 */
    printf( "primes is\n" );
    for ( i = 0; i < MAX_PRIME; i += 1 ) {
        if ( primes[ i ] == IS_PRIME ) {
            printf( "%d ", i );
        }
    }
    printf( "\n" );

    /* 表示を 10 の桁ごとに調べ、その素数の数だけを '*' で表示 */
    printf( "\nhistogram of primes is\n" );
    for ( i = 0; i < MAX_PRIME; i += 10 ) { /* 10 の桁ごとに処理する */
        printf( "%6d : ", i ); /* 処理桁を表示 */
        for ( j = i; j < i + 10; j += 1 ) { /* 10 の桁ごとの中を全て調べる */
            if ( primes[ j ] == IS_PRIME ) { /* それが素数ならば '*' を表示する */
                putchar( '*' );
            }
        }
        printf( "\n" );
    }

    return 0;
}

（11行目の step 変数宣言、20行目、23行目、25行目の printf( )、31行目の step 加算は、「エラトステネスのふるい」法が、いかに収束の早いアルゴリズムであるかを示すためのもので、削除しても動作には問題ありません；ちなみに 4行目の 1000 を 10000 にしても、たいした処理ステップにはなりません）

特に、サンプルの 18行目から 32行目までを、よくご覧下さい。　この部分が、「エラトステネスのふるい」を、私なりに忠実に C で書き表したものです。

紙に１から１００までの「領域」と、変数 check_prime の「領域」と、変数 i の「領域」を書いて、
そして変数 sqrt_max_prime の「領域」には、１００のルート、つまり 10 を書き込んでおいてから、
「自分がコンピューターになったつもりで」、紙と鉛筆（シャーペン）と消しゴムを使い、このプログラムを「頭と手で」１行ずつ、ていねいに実行してみてください。
まさに「エラトステネスのふるい」の動作そのものだ、という感じがしたと思いますが、いかがでしょうか……。

さて、これで素数は求まりましたが、次の問題である「表示を10の桁ごとに数え、その素数の数だけを’＊’で表示」が待っています。
これはサンプルの 44～53行目が相当します。
「10の桁ごとに」というのは、おそらく、00台、10台、20台、30台、40台、50台、60台、70台、80台、90台、100台、110台、……ごとに、という事だと私は解釈しました。　つまりこれは「『10 ごとの素数の個数』の度数分布を表示せよ」ということでしょう。

そうと決まればプログラミングはさほど難しくありません。　10台ごとに処理するループを回して、１ループの中で 0～9 の１０個について、それぞれ素数かどうか判定し、素数なら '*' を表示するだけです。
もちろん 10台ごとの改行を忘れてはいけません。
これで度数分布表（ヒストグラム）の完成です。

以上、ご参考になれば幸いです。

Answer 4

表示を10の桁ごとに数え、その素数の数だけを’＊’で表示させたい。

この記述の意味がわかりませんでした。以下を理解して書き直すとよいのではないでしょうか。

#include <stdio.h>
#define MAX_PRIME 1000

int main(void) {
    int primes[MAX_PRIME] = {0};
    int i, j, cnt = 2, isprime;
    primes[0] = 2;
    primes[1] = 3;
    printf("%d\n", primes[0]);
    printf("%d\n", primes[1]);

    for (i = 5; i <= MAX_PRIME; i += 2) {
        isprime = -1;

        for (j = 1; j < cnt && primes[j] * primes[j] <= i; j++) {
            if (i % primes[j] == 0) {
                isprime = 0;
                break;
            }
        }

        if (isprime) {
            printf("%d\n", i);
            primes[cnt++] = i;
        }
    }

    return 0;
}

Comments

[nanashi_09]

ありがとうございます。自分なりに考えてみます。