C++で数値がピタゴラス素数かどうかを判定する方法

本記事では、ある数がピタゴラス素数（Pythagorean Prime）であるかどうかをC++で判定する方法を解説します。ロジックの詳細に入る前に、まずピタゴラス素数とはどのような数なのかを見ていきましょう。

ピタゴラス素数とは？

ピタゴラス素数とは、4n + 1 の形で表すことができる素数のことです。つまり、ある数がピタゴラス素数であるかを調べるには、次の2つの条件を確認します。

1. その数が素数であること
2. その数を4で割った余りが1であること

この両方の条件を満たせば、その数はピタゴラス素数です。ピタゴラス素数の例としては、{5, 13, 17, 29, 37, 41, 53, …} などが挙げられます。

判定のアルゴリズム

判定の手順は以下の通りです。

1. 入力された数値 n が素数かどうかを判定する
2. 素数であれば、n を4で割った余りを計算する
3. 余りが1ならピタゴラス素数、それ以外はピタゴラス素数ではない

サンプルコード

#include <iostream>
using namespace std;

// 素数判定関数
bool isPrime(int n){
    for(int i = 2; i <= n/2; i++){
        if(n % i == 0){
            return false;
        }
    }
    return true;
}

// ピタゴラス素数判定関数
bool isPythagoreanPrime(int n) {
    if(isPrime(n) && ((n % 4) == 1)){
        return true;
    }
    return false;
}

int main() {
    int num = 29;
    if(isPythagoreanPrime(num)){
        cout << "この数はピタゴラス素数です";
    }else{
        cout << "この数はピタゴラス素数ではありません";
    }
}

実行結果

この数はピタゴラス素数です

コードの解説

isPrime 関数は、2から n/2 までの整数で順番に割り切れるかどうかを確認する、シンプルな試し割り法による素数判定を行います。isPythagoreanPrime 関数では、この素数判定の結果と「4で割った余りが1」という条件を論理ANDで組み合わせることで、ピタゴラス素数であるかを総合的に判定しています。

上記の例では num = 29 を渡しています。29は素数であり、29 ÷ 4 の余りは1なので、「この数はピタゴラス素数です」と出力されます。

補足：より効率的な素数判定について

今回の素数判定は n/2 までループする実装のため、大きな数値に対しては処理時間が長くなります。パフォーマンスを改善したい場合は、判定範囲を √n までに抑える方法や、エラトステネスの篩などのアルゴリズムを活用すると効果的です。