素数であるものを全て出力

Question

###実現したいこと
標準入力から1個の正整数 n ( 1 ＜ n ≦ 10の7乗） が与えられる。 2 から n までの整数の中で素数であるものを全て洗い出す。洗い出した素数について、つぎに示す通りのものを書き出すプログラム。
n が 100 未満のときは、洗い出した素数全てを小さい方から順に標準出力に書き出す。 このとき、それぞれの素数は、空白1文字に続けて必要最小限の桁数で書き出す。(したがって、行の最初には空白1文字が書き出されることになる。） そして、最後の素数を書き出した直後に改行を書き出すこと。
n が100以上のときは、洗い出した素数の個数とその最大の素数とをこの順に標準出力に書き出す。 二つの数値は、それぞれ必要最小限の桁数で左詰にして1行として書き出すこと。
###実行例
標準入力
10
標準出力
2 3 5 7
標準入力
30
標準出力
2 3 5 7 11 13 17 19 23 29
標準入力
100
標準出力
25
97

作成したソースコード

#include <stdio.h>
int main(int argc, char *argv[]){
   int n; scanf("%d",&n);
   int num[n+1];
   int i, k;
   for(i= 2; i<=n; i++) num[i]= i;
   for(k= 2; k<=n; k++){
　　　　　　　
　　　※この部分から不明です
　　　　　　　　↓
       ▶︎ その数が消されていなければ　　　　　　　　　
           ● その数 k の右に k ずつ進んで数を消す
   }
   
   ▶ n が 100 未満なら
       ● 素数を全て書き出す
    そうでないなら
       ● 個数と最大の素数を書き出す
   return 0;
}

そもそも間違っているならご指摘頂きたく。

Comments

[y_waiwai]

そのコードではどういう動作をするんでしょうか

、、ってコード作成依頼ですかｗ

[cateye]

int num[n+1]; ←動的配列ですが良いのですか？
100程度なら通常の配列でいけますよｄ＾＾
もし、10の7乗と言うなら10000000はint(32bit)にして３８Mbほどに成りますが・・・いいのですか？

[退会済みユーザー]

なんで質問内容削除するかなぁ。。。

Answer 1

未解決ということは、エラトステネスの篩（ふるい）の手順を作れていないのかな。
たとえば n == 50 としたら、int num[50 + 1]; という51要素の配列を用意し、50（num[50]）までの数字を検査する、のですよね。

プログラムを考える時、最初から、頭の中だけで、抽象的に考えようとするのはシンドイものです。手も動かして、紙に書き（描き）出してみると良いです。どんな処理をするのか、できるだけ具体的に書いてみるとこんな感じです（あくまで私なりの整理ですが）。質問者もこのようなシミュレーションを自分の手でやってみると良いと思います。

最初に num[2] = 2; 〜 num[50] = 50; と初期化しますね。これは私的に言えば** 2 〜 50 の全てを素数の候補とする**という意味です。

次に、for(k= 2; k<=n; k++)　で k の値を変化させながら、繰り返し何かをする。それは合成数を「消し」ていく処理です。そのひとつひとつを書き出すと、こういうことです。

• k == 2 の時、num[2] はそのまま、num[4], num[6], num[8], ... は素数でない（消す）
• k == 3 の時、num[3] はそのまま、num[6], num[9], num[12], ... は素数でない（消す）
• k == 4 の時、num[4] はそのまま、num[8], num[12], num[16], ... は素数でない（消す）
• k == 5 の時、num[5] はそのまま、num[10], num[15], num[20], ... は素数でない（消す）
• k == 6 の時、・・・

たとえば k == 2 の時、num[4], num[6], num[8], ... num[50] を消す＝素数でなくする処理を繰り返すので、これもまたループです。つまり、for ループの中にループを書いて、全体は二重のループで篩を実現できることを意味します。中のループも for ループで書けますが for に拘る必要はありません。

では、「素数でない、消す」とは具体的にどうすることか。
たとえば num[4] = 4; と初期化したのは 4 も素数候補にしたのでした。もちろん 4 は素数ではないので、まもなく「消し」て候補から外しますが、それは num[4] を配列から抜き去るという意味ではありません（いや、抜きたくても、できない笑）。

この場合、num[4] を消すとはバツ印をつけるイメージです。よくやる手は num[4] に 0 とか -1 のような値を代入する事です。ここでは 0 という値をバツ印として代入してみましょう。
そのまま何もしない num[2], num[3] などは、初期化した時点の 2, 3 という値が最後まで残ります。そして、そのような数は素数というわけです。

プログラムの後半では、整数 i が素数かどうかを調べる必要があります。
num[i] の値が 0 かどうかを調べれば判断がつくということ。

ともかく、k == 2 の場合 num[4], num[6], num[8], ... num[50] にバツをつけるようなループ・・・どうですか、ループは見えてきましたか？

なお、「そのまま」とは、たとえば k == 2 の時、num[2] に対して何もしないという事。その時点の値（それは 0 かもしれない）がそのまま残ります。

そもそも間違っているならご指摘頂きたく

「▶︎ その数が消されていなければ・・・」とするなら判断・検査することを意味しますが、素数でないとして消す時に、既に消されているかどうか（値が 0 か否か）を考慮する必要があるでしょうか。ありませんね。無条件に消して構わないのです。また、何度バツ印をつけようがバツ印に違いはありません。要するに、そのような判断・検査をする必要はありません。

なお、このようにプログラムの要所要所に、するべき事・処理の概要を予め書く、そののち実際のコードを書く、というのはコーディングの進め方として大変良いやり方です。つまり、コメントとしてプログラム中に残すのです。これを意識的に身につけることをおすすめします。プログラムを書く・保守するのが人間である以上、コメントはプログラムの中の重要な要素です。

ということで、疑問点は聞いてください。

Comments

[rubato6809]

１０の７乗なの？　いつの間に。それだと話が違ってきますね。
篩だとメモリ効率悪いからやり方変えたほうがよさそう。

Answer 2

※この部分から不明です

『エラトステネスの篩』で、検索しましょう。

過去作ったものですが・・・

/*
 * エラトステネスの篩本体 O(n log log n)
 */
void SieveOfEratosthenes(long arry[], long siz)
{
    long lim = (long)(ceil(sqrt(siz+2)));  // 最大値の平方根+αまで調べればいい
    for (long i = 2; i < lim; i++) {
        if (arry[i]) {
            long tmp = arry[i];  // 素数を取り出す
            for (long j = i + i; j < siz; j += tmp) {
                arry[j] = 0;  // 素数の倍数をクリア
            }
        }
    }
}

１０億までで（表示は別にして）私の環境（AMD Ryzen 5 1600X,Linux mint+Clang10）で２３秒程度かかります。

Comments

[cateye]

１０億までの素数は、50,847,534あります。

[退会済みユーザー]

> (long)(ceil(sqrt(siz+2))); // 最大値の平方根+αまで調べればいい

最大値まで調べなくてはまずくないですか？

[cateye]

→http://szarny.hatenablog.com/entry/2017/09/28/003352

[退会済みユーザー]

失礼。arry[] と勘違いしてました。

[cateye]

ちなみに領域(arry)は、calloc()で確保していますが、１０億だと１Gぐらい使いますね。

[退会済みユーザー]

C だと 10 億でも現実的な範囲なんですね。面白い。
勉強になりました。

[cateye]

実際はOSとかの制限が有ると思います。また、charにすれば1/8になりますが、インデックス管理がめんどくさいので、全部（０〜１０億まで）数値で埋めています。longは６４ビット有るので９００京まで行けるんですが、流石に１００億だと１０G使うので・・・××；

Answer 3

エラトステネスの篩を使えば、メモリは 10Mバイトで十分です。

#include <stdio.h>

char a[10000001];

int main(void)
{
	for (int i = 2; i <= 3163; i++)  // 3163 x 3163 = 10004569
		for (int j = i + i; j <= 10000000; j += i) a[j] = 1;
	int n;
	while (printf("n: "), scanf("%d", &n) == 1) {
		if (n < 100) {
			for (int i = 2; i < n; i++)
				if (a[i] == 0) printf(" %d", i);
			putchar('\n');
		}
		else {
			int c = 0, p;
			for (int i = 2; i <= n; i++)
				if (a[i] == 0) c++, p = i;
			printf("%d %d\n", c, p);
		}
	}
}

素数の真偽をビットで表現すればメモリは 8分の 1 で済みますが、
シフトとマスクによるビット参照で時間はかかるでしょう。

Comments

[退会済みユーザー]

ご回答有難うございます☻
解決しました！！

Answer 4

解決することができました。

Answer 5

C は書けませんが、なぜか回答依頼を頂いていたので、php で素数を求めるコードを書いてみました。

<?php
$max = 107;
$result[2] = true;
for($i = 3 ; $i <= $max ; $i += 2){
    $result[$i] = true;
}
foreach($result as $k => $v){
    for($i = $k ; $i * $k <= $max ; $i++){
        unset($result[$i * $k]);
    } 
}
echo join(' ,', array_keys($result));

『エラトステネスの篩』を実装してみたかっただけなので、全然仕様は満たしてませんが参考になれば。

#追記
107 じゃなくて、10 の 7 乗ですか。。。
その数だと、『エラトステネスの篩』だけだと多分工夫が足りないでしょうね。

某オンライン系のプログラミングサービスだとメモリが足りなくなるので、少し修正してみました。(かっこ悪いwww)
多分似たようなことを実装できれば、回答に辿りつけると思います。

<?php
$max = 10**7;
$result[2] = true;
$result[3] = true;
$result[5] = true;
$result[7] = true;
for($i = 3 ; $i <= $max ; $i += 2){
    if($i % 3 === 0 || $i % 5 === 0 || $i % 7 === 0){
        continue;
    }
    $result[$i] = true;
}
foreach($result as $k => $v){
    for($i = $k ; $i * $k <= $max ; $i++){
        unset($result[$i * $k]);
    } 
}
echo count(array_keys($result)).PHP_EOL;
echo join(' ,', array_keys($result));