C++로 어떤 수가 프로스 수(Proth Number)인지 판별하는 방법

하나의 수 'n'이 주어졌을 때, 해당 양의 정수가 프로스 수인지 아닌지를 판별하고 그 결과를 출력하는 것이 이번 글의 목표입니다.

프로스 수란 무엇인가?

프로스 수는 다음과 같은 형태로 정의되는 수입니다.

N = k · 2n + 1

여기서 n은 양의 정수, k는 홀수인 양의 정수입니다.

처음 몇 개의 프로스 수는 다음과 같습니다.

3, 5, 9, 13, 17, 25, 33, 41, 49, 57, 65, 81, 97.......

입력 예시

number: 17

출력

프로스 수입니다

입력 예시

number: 18

출력

프로스 수가 아닙니다

프로그램의 접근 방식

• 판별할 수를 입력받습니다.

• 정의된 공식을 적용하여 해당 수가 프로스 수인지 검사합니다.

• 조건이 참이면 "프로스 수입니다"를 출력합니다.

• 조건이 거짓이면 "프로스 수가 아닙니다"를 출력합니다.

알고리즘

Step 1 → 2의 거듭제곱 여부를 계산하는 함수 선언
    bool isPower(int num)
        return (num && !(num & (num - 1)))
Step 2 → 수가 프로스 수인지 확인하는 함수 선언
    bool isProth(int num)
        int k = 1 선언
        While (k < (num / k))
            IF (num % k == 0)
                IF (isPower(num / k))
                    return true
                End
                k = k + 2 설정
            End
        End
        return false
Step 3 → main() 함수에서
        int num = 17 선언
        IF (isProth(num - 1))
            "프로스 수입니다" 출력
        End
        Else
            "프로스 수가 아닙니다" 출력
End

예제 코드

#include <bits/stdc++.h>
using namespace std;
// 2의 거듭제곱 여부를 확인하는 함수
bool isPower(int num){
    return (num && !(num & (num - 1)));
}
// 수가 프로스 수인지 확인하는 함수
bool isProth(int num){
    int k = 1;
    while (k < (num / k)){
        if (num % k == 0){
            if (isPower(num / k))
                return true;
        }
        k = k + 2;
    }
    return false;
}
int main(){
    int num = 17;
    if (isProth(num - 1))
        cout << "프로스 수입니다";
    else
        cout << "프로스 수가 아닙니다";
    return 0;
}

코드 설명

• isPower() 함수: 비트 연산을 활용해 수가 2의 거듭제곱인지 확인합니다. num과 num - 1을 비트 AND 연산한 결과가 0이라면 num은 2의 거듭제곱입니다.

• isProth() 함수: 홀수 k를 1부터 증가시키며 num을 나누어 떨어지는지 검사합니다. 이때 몫(num/k)이 2의 거듭제곱이라면 해당 수는 k·2ⁿ 형태로 표현할 수 있으므로 프로스 수입니다.

• main() 함수: num - 1을 인자로 전달하는 이유는 프로스 수가 k·2ⁿ+1 형태이기 때문입니다. 즉, num−1이 k·2ⁿ으로 표현되는지 확인하면 num이 프로스 수인지 알 수 있습니다. 예를 들어 17은 1·2⁴+1이므로 프로스 수입니다.

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

프로스 수입니다