C++에서 주어진 숫자가 프로닉 수(Pronic Number)인지 판별하는 방법

프로닉 수(Pronic Number)란 무엇인가?

이번 글에서는 C++을 활용해 주어진 숫자가 프로닉 수(Pronic Number)인지 판별하는 방법을 살펴보겠습니다. 프로닉 수란 여러 개의 점을 직사각형 모양으로 배열할 수 있는 수를 말합니다.

프로닉 수는 수학적으로 두 개의 연속된 정수의 곱으로 정의됩니다. 즉, 어떤 수 n이 n = x × (x + 1) 형태로 표현될 수 있다면 그 수는 프로닉 수입니다.

처음 몇 가지 프로닉 수는 다음과 같습니다.

0, 2, 6, 12, 20, 30, 42, 56, 72, 90, 110, 132, 156, 182, 210, 240, 272, 306, 342

C++ 구현 코드

아래 코드는 isPronicNumber() 함수를 사용하여 0부터 200 사이의 모든 프로닉 수를 찾아 출력합니다. 함수 내부에서는 0부터 √num까지의 값 i에 대해 num == i * (i + 1) 조건을 검사하여 해당 수가 프로닉 수인지 확인합니다.

#include <iostream>
#include <cmath>
using namespace std;
bool isPronicNumber(int num) {
    for (int i = 0; i <= (int)(sqrt(num)); i++)
        if (num == i * (i + 1))
            return true;
    return false;
}
int main() {
    for (int i = 0; i <= 200; i++)
    if (isPronicNumber(i))
        cout << i << " ";
}

실행 결과

0 2 6 12 20 30 42 56 72 90 110 132 156 182

알고리즘 동작 원리

isPronicNumber() 함수는 입력받은 수의 제곱근(√n)까지만 반복문을 수행하기 때문에 시간 복잡도가 O(√n)으로 매우 효율적입니다. n = x(x + 1)를 만족하는 x는 항상 √n 이하의 값을 가지므로, 불필요한 반복 없이 빠르게 프로닉 수 여부를 판별할 수 있습니다.