素数を求めるプログラム

q14203072519.c

/**
 * @file        q14203072519.c
 * @brief       素数を求めるプログラム
 * @author      Keitetsu
 * @date        2019/02/06
 * @copyright   Copyright (c) 2019 Keitetsu
 * @par         License
 *              This software is released under the MIT License.
 */

#include <stdio.h>

#define ID      "q14203072519"
#define NAME    "ID非公開さん"

#define MAX     1000
#define scanf_s scanf


int main(void)
{
    int n; // 求める素数の最大値
    int primes[MAX];

    // 関数scanf等を使って，求める素数の最大値（<MAX）を入力する
    do {
        printf("n = ");
        scanf_s("%d", &n);
    } while (n >= MAX);

    // primesの要素を初期設定する．添字2～nの値を1にする．
    for (int i = 2; i <= n; i++) {
        primes[i] = 1;
    }

    // 「エラトステネスのふるい」による処理
    for (int i = 2; i <= n; i++) { // n以下の添字iに対して以下の処理
        if (primes[i] == 1) { // iが素数
            // 添字がiの倍数(iは除く）のprimesの値を0にする．
            for (int j = i + i; j <= n; j += i) {
                primes[j] = 0;
            }
        }
    } // end for
    // 処理が終了したら，primesの各要素の値は以下のようになる．
    // primes[i] = 0; iが素数でないとき
    // primes[i] = 1; iが素数のとき

    // primes[i] = 1 となるiを出力する ( i<=n )．
    for (int i = 2; i <= n; i++) {
        if (primes[i] == 1) {
            printf("%d ", i); // 素数のみ出力
        }
    }
    printf("\n");

    printf("ID: %s, NAME: %s\n", ID, NAME);

    return 0;
} // end of main