Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++ 프라임 포인트 완벽 가이드: 숫자를 두 개의 소수로 나누는 위치 찾기

이 문제에서는 하나의 숫자 N이 주어집니다. 우리의 목표는 이 숫자의 모든 프라임 포인트(prime point)를 찾아 출력하는 것이며, 만약 프라임 포인트가 하나도 존재하지 않는다면 -1을 출력해야 합니다.

프라임 포인트란 숫자를 특정 인덱스 위치에서 왼쪽과 오른쪽 두 부분으로 나누었을 때, 양쪽 숫자가 모두 소수(prime number)가 되도록 하는 인덱스 값을 말합니다.

구체적인 예시를 통해 문제를 이해해 보겠습니다.

입력: 2359
출력: 1

설명: 숫자 2359를 인덱스 1 위치에서 나누면 왼쪽은 2, 오른쪽은 59가 됩니다. 두 숫자 모두 소수이므로 인덱스 1이 프라임 포인트입니다.

문제 해결 접근 방법

이 문제는 다음과 같은 단계로 해결할 수 있습니다.

  1. 숫자의 자릿수를 계산하여 분할이 가능한지 확인합니다. 자릿수가 1 또는 2인 경우에는 두 개의 숫자로 나눌 수 없으므로 바로 -1을 출력합니다.
  2. 가능한 모든 분할 지점(인덱스)을 순회하면서 왼쪽 부분과 오른쪽 부분을 추출합니다.
  3. 추출된 두 숫자가 각각 소수인지 검사하고, 둘 다 소수라면 해당 인덱스를 프라임 포인트로 출력합니다.
  4. 모든 인덱스를 확인한 후에도 프라임 포인트를 찾지 못했다면 -1을 출력합니다.

소수 판별은 6k±1 최적화 기법을 활용하면 효율적으로 처리할 수 있습니다. 아래 코드는 이 솔루션의 전체 구현을 보여줍니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;

// 숫자의 자릿수를 계산하는 함수
int countDigits(int n) {
    int count = 0;
    while (n > 0){
        count++;
        n = n/10;
    }
    return count;
}

// 소수 여부를 검사하는 함수 (6k±1 최적화 적용)
int checkPrime(int n) {
    if (n <= 1)
        return -1;
    if (n <= 3)
        return 0;
    if (n%2 == 0 || n%3 == 0)
        return -1;
    for (int i=5; i*i<=n; i=i+6)
        if (n%i == 0 || n%(i+2) == 0)
            return -1;
    return 0;
}

// 프라임 포인트를 찾아 출력하는 함수
void primePoints(int n) {
    int count = countDigits(n);
    // 자릿수가 1 또는 2이면 분할 불가
    if (count==1 || count==2){
        cout << "-1";
        return;
    }
    bool found = false;
    for (int i=1; i<(count-1); i++){
        int left = n / ((int)pow(10,count-i));
        int right = n % ((int)pow(10,count-i-1));
        // 좌측과 우측이 모두 소수인 경우
        if (checkPrime(left) == 0 && checkPrime(right) == 0){
            cout<<i<<"\t";
            found = true;
        }
    }
    if (found == false)
        cout << "-1";
}

int main() {
    int N = 2359;
    cout<<"All prime divisions of number "<<N<<" are :\n";
    primePoints(N);
    return 0;
}

실행 결과

All prime divisions of number 2359 are :
1

코드 상세 설명

countDigits 함수: 매개변수로 받은 숫자의 자릿수를 계산합니다. 숫자를 10으로 반복해서 나누면서 카운트를 증가시키는 방식으로 동작합니다.

checkPrime 함수: 주어진 숫자가 소수인지 판별합니다. 2와 3으로 나누어 떨어지는지 먼저 확인한 후, 5부터 √n까지 6씩 증가시키며 i와 i+2로 나누어 떨어지는지 검사합니다. 이는 모든 소수가 6k±1 형태로 표현된다는 성질을 이용한 최적화 기법입니다.

primePoints 함수: 프라임 포인트를 찾는 핵심 로직입니다. pow 함수를 이용해 각 인덱스에서 숫자를 좌측과 우측으로 분할한 뒤, 두 숫자가 모두 소수인지 확인하여 조건을 만족하는 인덱스를 출력합니다.

마무리

이 알고리즘의 시간 복잡도는 자릿수를 d라고 할 때 O(d × √N)입니다. 각 분할 지점마다 소수 판별을 수행해야 하기 때문입니다. 숫자의 길이가 길어질수록 소수 판별 비용이 커지므로, 큰 수를 다룰 때는 에라토스테네스의 체와 같은 다른 기법을 함께 고려해 보는 것도 좋습니다.