C++로 N번째 비제곱수(Non-Square Number) 찾기

2, 3, 5, 7, 8처럼 어떤 수의 제곱이 아닌 숫자들이 있다는 것은 누구나 알고 있습니다. 비제곱수는 무한히 많아서 모든 숫자를 일일이 외울 수는 없습니다. 이 글에서는 비제곱수(non-square number)가 무엇인지 설명하고, C++에서 N번째 비제곱수를 찾는 방법을 단계별로 자세히 다뤄보겠습니다.

N번째 비제곱수란?

어떤 수가 정수의 제곱이라면 그 수를 완전제곱수(perfect square)라고 부릅니다. 완전제곱수의 대표적인 예시는 다음과 같습니다.

1은 1의 제곱
4는 2의 제곱
9는 3의 제곱
16은 4의 제곱
25는 5의 제곱

반대로 정수의 제곱이 아닌 수를 비제곱수(non-square number)라고 합니다. 예를 들어 처음 15개의 비제곱수는 다음과 같습니다.

2, 3, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 17, 18, 19

N번째 비제곱수를 찾는 방법

다음은 N번째 비제곱수를 찾는 입력·출력 예시입니다.

입력 : 2
출력 : 3
설명 : 첫 번째 비제곱수인 2 다음의 3이 두 번째 비제곱수입니다.

입력 : 5
출력 : 7
설명 : 앞의 네 개 비제곱수 2, 3, 5, 6 다음의 7이 다섯 번째 비제곱수입니다.

위 예시를 보면 해결 아이디어를 도출할 수 있습니다. N번째 비제곱수를 찾으려면 2부터 차례대로 각 정수가 완전제곱수인지 검사하고, 완전제곱수라면 카운트에서 제외한 채로 비제곱수만 세어 나가면 됩니다.

C++ 프로그램으로 N번째 비제곱수 찾기

아래는 C++로 N번째 비제곱수를 찾는 전체 코드입니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n; // 사용자로부터 입력을 받습니다.
    int i = 2; // 0과 1은 자기 자신의 제곱이므로 2부터 계산을 시작합니다.
    int cnt = 0; // 카운터 변수 선언
    while(cnt != n){ // 카운터 값이 n과 같아지면 반복문이 종료됩니다.
        int a = sqrt(i);
        if(i != a*a)
            cnt++;
        if(cnt != n)
            i++;
    }
    cout << i << "\n"; // n번째 비제곱수를 출력합니다.
}

실행 결과

5

(입력으로 3을 주면 출력으로 5를 얻습니다)

이제 위 코드의 동작 과정을 단계별로 살펴보겠습니다.

1단계 − 사용자로부터 입력을 받고 필요한 변수를 초기화합니다.

cin >> n; // 사용자로부터 입력을 받습니다.
int i = 2; // 0과 1은 자기 자신의 제곱이므로 2부터 계산을 시작합니다.
int cnt = 0; // 카운터 변수 선언

2단계 − 비제곱수만 세고 완전제곱수는 건너뜁니다.

while(cnt != n) { // 카운터 값이 n과 같아지면 반복문이 종료됩니다.
    int a = sqrt(i); // sqrt() 함수로 제곱근을 구합니다.
    if(i != a*a) // 해당 수가 완전제곱수인지 확인합니다.
        cnt++; // 완전제곱수가 아니면 카운터를 증가시킵니다.
    if(cnt != n)
        i++;
}

3단계 − N번째 비제곱수를 출력합니다.

cout << i << "\n"; // n번째 비제곱수를 출력합니다.

더 효율적인 방법: 수학 공식 활용하기

반복문으로 하나씩 검사하는 방법은 직관적이지만, N이 커지면 실행 시간이 길어질 수 있습니다. 다행히 N번째 비제곱수를 한 번의 계산으로 구하는 공식이 존재합니다.

N번째 비제곱수 = N + round(sqrt(N))

즉, N에 √N을 반올림한 값을 더하면 됩니다. 실제로 확인해 보면 N=5일 때 5 + round(√5) = 5 + 2 = 7로, 앞서 반복문으로 구한 결과와 일치합니다. 이 공식을 사용하면 O(1) 시간 복잡도로 즉시 답을 구할 수 있어 성능 면에서 훨씬 유리합니다.

마무리

이 글에서는 비제곱수의 개념과 함께 C++에서 N번째 비제곱수를 찾는 두 가지 방법, 즉 반복문 기반 구현과 수학 공식을 활용한 효율적인 접근법을 알아보았습니다. 이 로직은 C++뿐만 아니라 Java, Python, C 등 다른 프로그래밍 언어에서도 동일하게 적용할 수 있습니다. 최대한 쉽게 설명했으니 여러분의 학습에 도움이 되기를 바랍니다.