주어진 범위 내 인접 소수 간 거리 찾기

주어진 정수 범위 [L, R] 내에서 서로 가장 가까운 두 소수와 가장 먼 두 소수를 찾는 문제를 다룹니다. 이 문제는 에라토스테네스의 체와 분할 체(Segmented Sieve) 기법을 활용하여 효율적으로 해결할 수 있습니다.

알고리즘 개요

  1. 작은 소수들을 위한 에라토스테네스의 체 실행:

    [L, R] 범위의 수들을 체로 거르기 위해서는 R의 제곱근(sqrt(R))까지의 모든 소수가 필요합니다. 예를 들어, R이 2 * 10^9까지 가능하므로 sqrt(R)은 대략 44721입니다. 따라서 50000 정도의 상한까지 에라토스테네스의 체를 실행하여 모든 소수를 미리 찾아둡니다.

    #include <iostream>
#include <vector>
#include <algorithm> // For std::fill and std::max

// MAX_SQRT_R은 R의 최대값(2*10^9)의 제곱근인 약 44721보다 큰 값으로 설정합니다.
const int MAX_SQRT_R_BOUND = 50000; 
int smallPrimesStorage[MAX_SQRT_R_BOUND];
bool isSmallComposite[MAX_SQRT_R_BOUND + 1];

// 주어진 limit까지의 모든 소수를 찾아 smallPrimesStorage에 저장합니다.
void generateSmallPrimes(int limit, int& count) {
    std::fill(isSmallComposite, isSmallComposite + limit + 1, false);
    count = 0;
    for (int i = 2; i <= limit; ++i) {
        if (!isSmallComposite[i]) {
            smallPrimesStorage[count++] = i;
        }
        for (int j = 0; j < count && (long long)smallPrimesStorage[j] * i <= limit; ++j) {
            isSmallComposite[smallPrimesStorage[j] * i] = true;
            if (i % smallPrimesStorage[j] == 0) break;
        }
    }
}
  2. 분할 체를 이용한 범위 내 합성수 표시:

    미리 찾아둔 작은 소수들을 이용하여 [L, R] 범위 내의 모든 수를 합성수인지 아닌지 표시합니다. R - L + 1 크기의 불리언 배열 isRangeComposite를 선언하여 isRangeComposite[i]가 L + i가 합성수인지 나타내게 합니다.

    • 각 작은 소수 p에 대해:
      • p의 배수 중 L보다 크거나 같은 첫 번째 배수를 찾습니다. 이 시작점은 std::max(2LL * currentPrime, (minVal + currentPrime - 1) / currentPrime * currentPrime)로 계산할 수 있습니다. 2LL * currentPrime은 currentPrime 자신이 소수이므로, currentPrime을 합성수로 표시하지 않기 위함입니다. (minVal + currentPrime - 1) / currentPrime * currentPrime은 minVal보다 크거나 같은 currentPrime의 가장 작은 배수를 찾습니다.
      • 이 시작점부터 maxVal까지 currentPrime을 더해가며 isRangeComposite[j - minVal]을 true로 설정합니다.
    // minVal부터 maxVal까지의 범위에 대해 합성수를 표시합니다.
void applySegmentedSieve(int minVal, int maxVal, const int smallPrimes[], int smallPrimeCount, bool isRangeComposite[]) {
    std::fill(isRangeComposite, isRangeComposite + (maxVal - minVal + 1), false);
    for (int i = 0; i < smallPrimeCount; ++i) {
        long long currentPrime = smallPrimes[i];
        
        // currentPrime의 배수 중 minVal 이상인 첫 번째 수를 찾습니다.
        // currentPrime * currentPrime은 해당 소수가 처음으로 다른 합성수를 만드는 지점이며,
        // 그보다 작은 합성수는 이미 작은 소수들에 의해 걸러졌거나, p 자체가 소수입니다.
        // 그러나 L 값이 작을 경우 currentPrime*currentPrime이 L보다 작을 수 있습니다.
        // 그리고 2*currentPrime 보다 작은 수는 소수이거나 이미 걸러져야 합니다.
        // 따라서 minVal 이상인 배수 중에서 가장 작은 합성수(즉 2*p 이상)를 시작점으로 잡습니다.
        long long startMarking = std::max(2LL * currentPrime, (minVal + currentPrime - 1) / currentPrime * currentPrime);

        for (long long j = startMarking; j <= maxVal; j += currentPrime) {
            isRangeComposite[j - minVal] = true;
        }
    }
}
  3. 범위 내 소수 추출:

    isRangeComposite 배열을 순회하며 isRangeComposite[i]가 false이고 L + i가 2 이상인 경우, L + i는 소수입니다. 이 소수들을 별도의 리스트에 저장합니다.

    // isRangeComposite 배열을 바탕으로 실제 소수들을 추출하여 벡터에 저장합니다.
void collectPrimes(int minVal, int maxVal, const bool isRangeComposite[], std::vector<int>& primesInCurrentRange) {
    primesInCurrentRange.clear();
    for (int i = 0; i <= maxVal - minVal; ++i) {
        // isRangeComposite[i]가 false이고, 해당 수가 2 이상일 경우 소수입니다.
        if (!isRangeComposite[i]) {
            long long currentNum = (long long)minVal + i;
            if (currentNum >= 2) { 
                primesInCurrentRange.push_back((int)currentNum);
            }
        }
    }
}
  4. 최소/최대 거리 계산:

    추출된 소수 리스트를 순회하며 인접한 소수 쌍 간의 거리를 계산하고, 이 중 가장 작은 거리와 가장 큰 거리를 갖는 쌍을 찾습니다.

    int main() {
    std::ios_base::sync_with_stdio(false); // C++ 표준 스트림과 C 표준 스트림의 동기화 비활성화
    std::cin.tie(NULL); // cin과 cout의 묶음을 해제하여 입력 대기 없이 바로 출력 가능하게 설정

    int smallPrimeCount;
    generateSmallPrimes(MAX_SQRT_R_BOUND, smallPrimeCount); // 50000까지의 소수 미리 생성

    int L, R;
    // R - L의 최대값은 10^6이므로, 배열 크기는 10^6 + 1
    const int MAX_RANGE_SIZE = 1000001; 
    static bool isRangeComposite[MAX_RANGE_SIZE]; // 큰 배열이므로 static으로 선언하여 스택 오버플로우 방지
    std::vector<int> primesFoundInSegment;

    while (std::cin >> L >> R) {
        applySegmentedSieve(L, R, smallPrimesStorage, smallPrimeCount, isRangeComposite);
        collectPrimes(L, R, isRangeComposite, primesFoundInSegment);

        if (primesFoundInSegment.size() < 2) {
            std::cout << "There are no adjacent primes.\n";
        } else {
            int minDifference = 2e9 + 7; // 충분히 큰 초기값
            int maxDifference = -1; // 충분히 작은 초기값
            int closestP1 = -1, closestP2 = -1;
            int mostDistantP1 = -1, mostDistantP2 = -1;

            for (size_t i = 0; i + 1 < primesFoundInSegment.size(); ++i) {
                int currentDiff = primesFoundInSegment[i + 1] - primesFoundInSegment[i];
                if (currentDiff < minDifference) {
                    minDifference = currentDiff;
                    closestP1 = primesFoundInSegment[i];
                    closestP2 = primesFoundInSegment[i + 1];
                }
                if (currentDiff > maxDifference) {
                    maxDifference = currentDiff;
                    mostDistantP1 = primesFoundInSegment[i];
                    mostDistantP2 = primesFoundInSegment[i + 1];
                }
            }

            std::cout << closestP1 << "," << closestP2 << " are closest, "
                      << mostDistantP1 << "," << mostDistantP2 << " are most distant.\n";
        }
    }
    return 0;
}

이 구현은 R의 최댓값이 2 * 10^9이고 R-L의 최댓값이 10^6일 때 효율적으로 동작합니다. std::vector, std::algorithm, std::iostream 등의 표준 라이브러리가 활용됩니다.

N!의 소인수 분해: 각 소수의 지수 계산

주어진 정수 N에 대해 N! (N 팩토리얼)을 소인수 분해했을 때, 각 소수 p가 몇 번 곱해지는지 (즉, p의 지수)를 계산하는 방법을 알아봅니다. 이는 르장드르의 공식(Legendre's Formula)을 통해 효율적으로 수행할 수 있습니다.

르장드르의 공식

N!에 포함된 소수 p의 지수 E_p(N!)는 다음과 같이 계산됩니다:

E_p(N!) = floor(N/p) + floor(N/p^2) + floor(N/p^3) + ...

이 공식은 N!에 포함된 p의 모든 배수들, p^2의 배수들 등을 고려하여 p의 총 개수를 합산합니다. 예를 들어, 8!에 포함된 2의 지수는:

  • floor(8/2) = 4 (2, 4, 6, 8에 2가 최소 한 번 포함)
  • floor(8/4) = 2 (4, 8에 2가 최소 두 번 포함)
  • floor(8/8) = 1 (8에 2가 최소 세 번 포함)

따라서 8!에 2는 총 4 + 2 + 1 = 7번 포함됩니다.

알고리즘 구현

  1. N까지의 소수 찾기:

    먼저, N!에 포함될 수 있는 모든 소수 (N 이하의 소수)를 에라토스테네스의 체를 사용하여 찾습니다.

    #include <iostream>
#include <vector>
#include <algorithm> // For std::fill

const int MAX_FACTORIAL_INPUT = 1000000; // N up to 10^6
int primesForFactorial[MAX_FACTORIAL_INPUT];
int primeCountForFactorial;
bool isCompositeForFactorialSieve[MAX_FACTORIAL_INPUT + 1];

// 주어진 limit까지의 모든 소수를 찾아 primesForFactorial에 저장합니다.
void generatePrimesUpToN(int limit) {
    std::fill(isCompositeForFactorialSieve, isCompositeForFactorialSieve + limit + 1, false);
    primeCountForFactorial = 0;
    for (int i = 2; i <= limit; ++i) {
        if (!isCompositeForFactorialSieve[i]) {
            primesForFactorial[primeCountForFactorial++] = i;
        }
        for (int j = 0; j < primeCountForFactorial && (long long)primesForFactorial[j] * i <= limit; ++j) {
            isCompositeForFactorialSieve[primesForFactorial[j] * i] = true;
            if (i % primesForFactorial[j] == 0) break;
        }
    }
}
  2. 각 소수의 지수 계산 및 출력:

    찾은 각 소수 p에 대해, 르장드르의 공식을 적용하여 p의 지수를 계산하고 결과를 출력합니다.

    int main() {
    std::ios_base::sync_with_stdio(false); // 빠른 입출력 설정
    std::cin.tie(NULL); // 빠른 입출력 설정

    int inputNumber;
    std::cin >> inputNumber;
    generatePrimesUpToN(inputNumber); // inputNumber까지의 소수 찾기

    for (int i = 0; i < primeCountForFactorial; ++i) {
        int currentPrime = primesForFactorial[i];
        int primeExponent = 0;
        long long tempNumForCalculation = inputNumber; // N 값을 임시 변수에 복사하여 사용
        
        // 르장드르의 공식 적용: floor(N/p) + floor(N/p^2) + ...
        while (tempNumForCalculation > 0) {
            primeExponent += tempNumForCalculation / currentPrime;
            tempNumForCalculation /= currentPrime;
        }
        std::cout << currentPrime << " " << primeExponent << "\n";
    }

    return 0;
}

이 방법을 통해 N!의 모든 소인수와 그에 해당하는 지수를 효율적으로 얻을 수 있습니다. 코드에서는 C++ 표준 라이브러리와 빠른 입출력 설정을 활용했습니다.

태그: C++ 알고리즘 소수 분할체 에라토스테네스의체

7월 15일 17:32에 게시됨

인기 태그

©2026 괴물 클럽