C++로 숫자가 피타고라스 소수인지 판별하는 방법

이번 글에서는 어떤 숫자가 피타고라스 소수(Pythagorean Prime)인지 판별하는 C++ 프로그램을 살펴보겠습니다. 로직을 자세히 다루기 전에, 먼저 피타고라스 소수가 무엇인지 이해하는 것이 중요합니다.

피타고라스 소수란?

피타고라스 소수는 4n + 1 형태로 표현할 수 있는 소수를 의미합니다. 흥미로운 점은 이런 소수들이 두 제곱수의 합(a² + b²)으로도 나타낼 수 있다는 것인데, 예를 들어 5 = 1² + 2², 13 = 2² + 3²처럼 표현됩니다. 이러한 성질 때문에 피타고라스 정리와 연관 지어 '피타고라스 소수'라고 부릅니다.

판별 조건

어떤 수가 피타고라스 소수인지 확인하려면 다음 두 가지 조건을 모두 만족해야 합니다.

1. 해당 수가 소수여야 합니다.
2. 그 수를 4로 나누었을 때 나머지가 1이어야 합니다.

대표적인 피타고라스 소수는 {5, 13, 17, 29, 37, 41, 53, ...}과 같습니다.

C++ 구현 예제

#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 << "The number is Pythagorean Prime";
    }else{
        cout << "The number is not Pythagorean Prime";
    }
}

실행 결과

The number is Pythagorean Prime

코드 설명

isPrime() 함수는 2부터 n/2까지의 수로 나누어 보아 약수가 존재하는지 검사함으로써 소수 여부를 판별합니다. isPythagoreanPrime() 함수는 이 결과와 함께 n을 4로 나눈 나머지가 1인지를 함께 확인합니다.

예제에서 사용한 29는 소수이며, 29 ÷ 4의 나머지는 1입니다. 따라서 29는 피타고라스 소수에 해당하고, 프로그램 역시 이를 올바르게 출력하는 것을 확인할 수 있습니다.