C++로 소인수 거듭제곱의 GCD가 1인 범위 내 숫자 개수 구하기

두 수 start와 end가 양의 정수 범위를 나타낼 때, 이 범위 [start, end] 안에 속한 숫자 중 소인수분해했을 때 각 소인수의 지수(거듭제곱)들의 최대공약수(GCD)가 1이 되는 숫자의 개수를 구하는 것이 목표입니다.

예를 들어 어떤 수가 2^p × 3^q × 5^r … 형태로 소인수분해된다면, 지수 p, q, r …의 GCD는 반드시 1이 되어야 합니다.

예시로 이해하기

입력 예제 1

입력 – start = 1, end = 10

출력 – 소인수 거듭제곱의 GCD가 1인 숫자의 개수: 6

설명 – 해당하는 숫자는 다음과 같습니다.

2 (2¹), 3 (3¹), 5 (5¹), 7 (7¹), 8 (2³), 10 (2¹×5¹) — 각 숫자의 소인수 지수들은 모두 GCD가 1입니다.

입력 예제 2

입력 – start = 11, end = 20

출력 – 소인수 거듭제곱의 GCD가 1인 숫자의 개수: 9

설명 – 해당하는 숫자는 다음과 같습니다.

11 (11¹), 12 (3¹×2²), 13 (13¹), 14 (2¹×7¹), 15 (3¹×5¹), 17 (17¹), 18 (2¹×3²), 19 (19¹), 20 (2²×5¹) — 각 숫자의 소인수 지수들은 모두 GCD가 1입니다.

접근 방법

이 접근법의 핵심 아이디어는 간단합니다. 완전거듭제곱수(perfect power)가 아닌 수는 위 조건을 만족합니다. 완전거듭제곱수는 소인수 지수들의 GCD가 항상 1보다 크기 때문입니다. 따라서 범위 내의 완전거듭제곱수를 모두 찾아 전체 개수에서 빼주면 원하는 답을 얻을 수 있습니다.

정답 = (end − start + 1) − (범위 [start, end] 내 완전거듭제곱수의 개수)

범위 변수 start와 end를 입력받습니다.
지수가 3 이상인 거듭제곱수를 저장할 vector vec을 준비합니다.
완전제곱수(perfect square)를 저장할 set sett를 준비합니다.
완전제곱수가 아닌 홀수 거듭제곱수를 저장할 set sett_2를 준비합니다.
calculate() 함수는 vec, sett, sett_2를 채워 넣어 완전제곱수, 완전제곱수가 아닌 수, 지수가 3 이상인 거듭제곱수를 분류합니다.
i = 2부터 i < size까지 for 루프로 순회합니다.
완전제곱수 i*i를 sett에 삽입합니다.
sett.find(i) != sett.end()가 참이면 i 자체가 완전제곱수이므로 건너뜁니다.
현재 수의 거듭제곱 값이 large보다 작은 동안 while 루프를 실행합니다.
짝수 거듭제곱은 이미 완전제곱수(sett에 존재)이므로, 홀수 거듭제곱만 sett_2에 삽입합니다.
마지막으로 sett_2의 정렬된 값을 for 루프를 사용해 vector vec에 삽입합니다.
GCD_1(long int start, long int end) 함수는 범위를 입력받아 조건을 만족하는 숫자의 개수를 반환합니다.
calculate()를 호출합니다.
범위 내 완전제곱수의 개수를 계산합니다: per_sq = floor(sqrtl(end)) − floor(sqrtl(start − 1)).
upper_bound(vec.begin(), vec.end(), end) − vec.begin()으로 vec에서 end보다 큰 첫 번째 위치(top)를 구합니다.
마찬가지로 lower_bound(vec.begin(), vec.end(), start) − vec.begin()으로 start 이상인 첫 번째 위치(bottom)를 구합니다.
완전거듭제곱수의 개수를 계산합니다: per_pow = per_sq + (top − bottom).
정답은 count = (end − start + 1) − per_pow 입니다.
최종적으로 count를 결과로 반환합니다.

구현 코드

#include <bits/stdc++.h>
using namespace std;
#define size 1000005
#define large 1e18

vector < long int > vec;
set < long int > sett;
set < long int > sett_2;

void calculate() {
    for (long int i = 2; i < size; i++) {
        sett.insert(i * i);
        if (sett.find(i) != sett.end()) {
            continue;
        }
        long int total = i;
        while (i * i <= large / total) {
            total *= (i * i);
            sett_2.insert(total);
        }
    }
    for (auto it: sett_2) {
        vec.push_back(it);
    }
}

long int GCD_1(long int start, long int end) {
    calculate();

    long int per_sq = floor(sqrtl(end)) - floor(sqrtl(start - 1));
    long int top = upper_bound(vec.begin(), vec.end(), end) - vec.begin();
    long int bottom = lower_bound(vec.begin(), vec.end(), start) - vec.begin();
    long int per_pow = per_sq + (top - bottom);
    long int count = (end - start + 1) - per_pow;
    return count;
}
int main() {
    long int start = 10, end = 40;
    cout << "Count of numbers in a range having GCD of powers of prime factors equal to 1 are: " << GCD_1(start, end);
    return 0;
}

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

출력

Count of numbers in a range having GCD of powers of prime factors equal to 1 are: 7