C++로 1부터 N 사이에서 x와 x+1이 같은 개수의 양의 약수를 가지는 정수 x 찾기

정수 N이 주어졌을 때, 1 < x < N 범위 내에서 x와 x+1이 서로 같은 개수의 양의 약수를 가지는 정수 x의 개수를 구하는 문제입니다. 예를 들어 N = 3이라면 출력 결과는 1이 됩니다. 왜냐하면 1의 약수는 {1}, 2의 약수는 {1, 2}, 3의 약수는 {1, 3}으로, 여기서 조건을 만족하는 경우가 존재하기 때문입니다.

이 문제를 해결하기 위해서는 먼저 N 이하의 모든 수에 대해 약수의 개수를 계산하여 배열에 저장합니다. 그다음 반복문을 실행하면서 x와 x+1이 동일한 개수의 양의 약수를 가지는 정수 x의 개수를 세면 됩니다.

약수 개수 효율적으로 구하기

약수의 개수를 구할 때는 제곱근까지만 확인하는 방법을 사용하면 효율적입니다. i를 j로 나누어 떨어질 때 j와 i/j가 모두 약수이므로 약수 개수를 2씩 증가시키고, j² = i인 경우(완전제곱수)에는 중복을 피하기 위해 1만 증가시킵니다.

또한 누적 합 배열(pre)을 활용하면 특정 N에 대한 답을 O(1) 시간에 바로 조회할 수 있어 여러 쿼리를 처리할 때 매우 유용합니다.

예제 코드

#include<iostream>
#include<cmath>
#define N 100005
using namespace std;
int table[N], pre[N];
void findPositiveDivisor() {
    for (int i = 1; i < N; i++) {
        for (int j = 1; j * j <= i; j++) {
            if (i % j == 0) {
                if (j * j == i)
                    table[i]++;
                else
                    table[i] += 2;
            }
        }
    }
    int ans = 0;
    for (int i = 2; i < N; i++) {
        if (table[i] == table[i - 1])
        ans++;
        pre[i] = ans;
    }
}
int main() {
    findPositiveDivisor();
    int n = 15;
    cout << "Number of integers: " << pre[n] << endl;
}

출력 결과

Number of integers: 2

코드 설명

위 코드에서 findPositiveDivisor 함수는 두 가지 작업을 수행합니다. 첫 번째 단계에서는 1부터 N-1까지 각 수의 약수 개수를 table 배열에 저장하고, 두 번째 단계에서는 인접한 두 수의 약수 개수를 비교하여 조건을 만족하는 경우를 누적해 pre 배열에 기록합니다.

N = 15인 경우, 조건을 만족하는 수는 x = 2(약수 개수 1과 2... 실제로는 2와 3의 약수 개수가 각각 2로 동일)와 x = 14(14와 15의 약수 개수가 각각 4로 동일) 등으로 총 2개입니다. 따라서 출력값은 2가 됩니다.

이 알고리즘의 시간 복잡도는 전처리 과정에서 O(N√N)이며, 이후 각 쿼리는 O(1)에 처리됩니다. N이 최대 10만 정도일 때 충분히 빠르게 동작합니다.