C++에서 숫자가 쿼턴 소수(Quartan Prime)인지 확인하는 방법

쿼턴 소수(Quartan Prime)란?

쿼턴 소수는 네 번째 거듭제곱의 합, 즉 x⁴ + y⁴ 형태로 표현할 수 있는 소수를 말합니다. 이때 x와 y는 모두 0보다 커야 한다는 조건이 있습니다.

쿼턴 소수 판별 원리

주어진 숫자가 쿼턴 소수인지 확인하는 과정은 생각보다 간단합니다. 다음 두 단계만 거치면 됩니다.

1. 소수 여부 검사 — 먼저 해당 숫자가 소수(prime number)인지 확인합니다.
2. 나머지 연산 검사 — 소수라면 그 숫자를 16으로 나누었을 때 나머지가 1인지 검사합니다. 나머지가 1이면 쿼턴 소수입니다.

정리에 따르면 홀수인 쿼턴 소수는 반드시 16으로 나눈 나머지가 1이 됩니다. 대표적인 쿼턴 소수로는 {2, 17, 97, …}이 있으며, 여기서 2는 특수한 경우(1⁴ + 1⁴ = 2)에 해당합니다.

C++ 구현 예제

아래 코드는 위의 원리를 그대로 구현한 것입니다. isPrime() 함수로 소수 여부를 먼저 판별하고, isQuartanPrime() 함수에서 16으로 나눈 나머지가 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 isQuartanPrime(int n) {
    if(isPrime(n) && ((n % 16) == 1)){
        return true;
    }
    return false;
}

int main() {
    int num = 97;
    if(isQuartanPrime(num)){
        cout << "이 숫자는 쿼턴 소수입니다.";
    }else{
        cout << "이 숫자는 쿼턴 소수가 아닙니다.";
    }
}

실행 결과

이 숫자는 쿼턴 소수입니다.

코드 동작 설명

예제에서 사용된 숫자 97은 소수이며, 97을 16으로 나누면 몫이 6이고 나머지가 1입니다(97 = 16 × 6 + 1). 따라서 두 조건을 모두 만족하므로 97은 쿼턴 소수로 판별됩니다. 실제로 97은 2⁴ + 3⁴ = 16 + 81 = 97로 표현되기 때문에 x⁴ + y⁴ 형태임도 알 수 있습니다.

이처럼 소수 판별과 나머지 연산만으로 쿼턴 소수를 손쉽게 확인할 수 있습니다. 다만 숫자 2처럼 특수한 경우까지 완벽하게 처리하려면 별도의 조건 처리를 추가하는 것이 좋습니다.