【C言語】ある整数が2つの素数の和で表せるかどうかを判定するプログラム

問題概要

与えられた正の整数 N が、2つの素数の和として表現できるかどうかを判定するプログラムを、C言語で作成します。

例えば 20 は「3 + 17」や「13 + 7」というように、複数の素数の組み合わせで表すことができます。一方で、11 のように2つの素数の和として表せない数も存在します。

考え方

まず、具体例を使って考えてみましょう。

• 20 = 3 + 17(どちらも素数)
• 20 = 13 + 7(どちらも素数)

このように、ある数を2つの素数の和で表せるか調べるには、「小さい方の数 i」を 2 から順に増やしながら、「i と (N − i) がどちらも素数になる組み合わせが存在するか」を確認していきます。

なお、「4 以上のすべての偶数は2つの素数の和で表せる」とするゴールドバッハの予想は有名ですが、これは現在でも証明されていない未解決問題です。ただし、計算機による検証では非常に大きな範囲まで成立することが確認されています。

アルゴリズム

与えられた数を2つの素数の和として表現できるかを判定する手順は、以下の通りです。

1. 判定したい数を実行時に入力として受け取ります。
2. i = 2 から num / 2 まで繰り返します。
3. i が素数かどうかを判定します。
4. i が素数であれば、(num − i) も素数かどうかを判定します。
5. i と (num − i) の両方が素数であれば、その数は「i + (num − i)」という2つの素数の和として表現できます。

C言語によるサンプルプログラム

以下は、与えられた数を2つの素数の和として表現できるかどうかを判定するCプログラムです。

#include <stdio.h>

/* 素数なら 1、素数でなければ 0 を返す関数 */
int sum(int n);

int main(void){
    int num, i;
    printf("Enter number: ");
    scanf("%d", &num);

    int flag = 0;
    /* 小さい方の数 i を 2 から num/2 まで試す */
    for(i = 2; i <= num/2; ++i){
        if(sum(i) == 1){          /* i が素数 */
            if(sum(num - i) == 1){  /* num - i も素数 */
                printf("\nThe given %d can be expressed as the sum of %d and %d\n\n", num, i, num - i);
                flag = 1;
            }
        }
    }

    if(flag == 0)
        printf("The given %d cannot be expressed as the sum of two prime numbers\n", num);

    return 0;
}

/* 素数判定を行う関数 */
int sum(int n){
    int i, isPrime = 1;
    for(i = 2; i <= n/2; ++i){
        if(n % i == 0){
            isPrime = 0;
            break;
        }
    }
    return isPrime;
}

プログラムのポイント

• sum() 関数は、引数 n が素数であれば 1、そうでなければ 0 を返します。
• メイン処理では、i を 2 から num/2 まで動かし、i と (num − i) の両方が素数になる組み合わせを探します。
• 組み合わせが1つでも見つかれば結果を出力し、最後まで見つからなければ「2つの素数の和として表せない」と出力します。

実行結果

上記のプログラムを実行すると、次のような出力が得られます。

Run 1:
Enter number: 34
The given 34 can be expressed as the sum of 3 and 31
The given 34 can be expressed as the sum of 5 and 29
The given 34 can be expressed as the sum of 11 and 23
The given 34 can be expressed as the sum of 17 and 17

Run 2:
Enter number: 11
The given 11 cannot be expressed as the sum of two prime numbers

34 の場合、(3, 31)、(5, 29)、(11, 23)、(17, 17) の4通りの組み合わせが見つかります。一方、11 の場合は 2 + 9、3 + 8、5 + 6 のいずれも両方が素数にならないため、「2つの素数の和として表現できない」と判定されます。