【C言語】素数を1000個求めて出力するプログラムの書き方

この記事では、C言語を使って素数を求める方法と、素数を1000個求めるプログラムの書き方を紹介します。

目次から探す

素数の求め方

素数とは、1と自分自身以外の約数を持たない正の整数のことです。

素数を求める方法にはいくつかのアルゴリズムがありますが、ここでは「ブルートフォース法」と「エラトステネスの篩」について説明します。

方法1: ブルートフォース法

ブルートフォース法は、ある数が素数かどうかを判定するために、その数を2から順番に割っていき、割り切れる数が存在するかどうかを調べる方法です。

具体的な手順は以下の通りです。

  1. 判定したい数をnとする。
  2. nを2からn-1までの数で順番に割っていき、割り切れる数が存在するかどうかを調べる。
  3. 割り切れる数が存在しない場合、nは素数であると判定する。

この方法は非常に単純な方法ですが、大きな数に対しては効率が悪いため、計算時間がかかる可能性があります。

方法2: エラトステネスの篩

エラトステネスの篩は、ある範囲内の数から素数を見つけるための効率的な方法です。

具体的な手順は以下の通りです。

  1. 範囲内の数を表す配列を用意する。

初期値は全て「素数である」とする。

  1. 2から順番に数を取り出し、その数が素数である場合、その数の倍数を全て「素数ではない」とする。
  2. 繰り返し処理を行い、範囲内の数を順番に取り出して素数を見つける。

この方法は、範囲内の数を一度に判定するため、ブルートフォース法よりも効率的に素数を見つけることができます。

プログラムの実装

ブルートフォース法を用いた実装

#include <stdio.h>
int main() {
    int count = 0; // 素数の個数をカウントする変数
    int num = 2; // 判定する数の初期値
    while (count < 1000) {
        int isPrime = 1; // 素数かどうかを判定するフラグ
        for (int i = 2; i <= num / 2; i++) {
            if (num % i == 0) {
                isPrime = 0; // 割り切れる数が存在する場合、素数ではない
                break;
            }
        }
        if (isPrime) {
            printf("%d ", num);
            count++;
        }
        num++;
    }
    return 0;
}

上記のプログラムは、ブルートフォース法を用いて 1000 個の素数を求めるものです。

変数countを用いて素数の個数をカウントし、変数numを2から順番に増やしていきます。

内部のforループでは、numを2からnum/2までの数で割っていき、割り切れる数が存在するかどうかを調べます。

割り切れる数が存在しない場合、isPrimeを1に設定し、素数として出力します。

エラトステネスの篩を用いた実装

#include <stdio.h>
int main() {
    int count = 0; // 素数の個数をカウントする変数
    int primes[1000]; // 素数を格納する配列
    // 初期化
    for (int i = 0; i < 1000; i++) {
        primes[i] = 1; // 全ての数を素数として初期化
    }
    for (int i = 2; count < 1000; i++) {
        if (primes[i]) {
            printf("%d ", i);
            count++;
            // iの倍数を全て素数ではないとする
            for (int j = i * 2; j < 1000; j += i) {
                primes[j] = 0;
            }
        }
    }
    return 0;
}

上記のプログラムは、エラトステネスの篩を用いて1000個の素数を求めるものです。

配列primesを用意し、初期値を全て1(素数)とします。

外部のforループでは、2から順番に数を取り出し、その数が素数である場合に出力します。

また、その数の倍数を全て素数ではないとして配列primesの該当する要素を0に設定します。

目次から探す