모든 챌린지
보통 0명 해결 정답률 0%

골드바흐 분할

짝수를 두 소수의 합으로 나타내되, 첫 번째 소수가 가능한 한 작도록 합니다.

배우게 될 내용

  • √n에서 멈추는 시험 나눗셈 소수 판별을 작성할 수 있습니다
  • 후보를 작은 순서대로 탐색하고 처음 찾은 곳에서 멈출 수 있습니다
  • 요구하는 순서대로 쌍을 반환할 수 있습니다

문제

원문 보기 (영어)

골드바흐의 추측은 2보다 큰 모든 짝수를 두 소수의 합으로 나타낼 수 있다는 내용입니다. 아직 증명되지는 않았지만, 이 문제에 나오는 수보다 훨씬 큰 범위까지 성립함이 확인되었습니다. 나타내는 방법이 여러 가지인 경우도 많습니다. 예를 들어 28 = 5 + 23 = 11 + 17입니다. 그중 작은 쪽 소수가 가장 작은 것을 찾으세요.

goldbach_partition(n) 함수를 구현하세요.

p = 2, 3, 5, ... 순서로 시도하면서 n − p가 소수인지 확인하면 답을 금방 찾을 수 있습니다. 작은 p에서 거의 항상 성공하기 때문입니다. 10^9 이하의 수를 나눗셈으로 소수 판별할 때는 약 31,623까지만 나누어 보면 됩니다.

입력

n: 2보다 큰 짝수입니다.

출력

p와 q가 소수이고 p + q = n, p ≤ q이며, p가 이를 만족하는 가장 작은 소수가 되는 [p, q]를 반환합니다.

제약 조건

4 ≤ n ≤ 10^9, n은 짝수

예시

예시 1
입력:
n = 28

예상 출력:
expected = [5, 23]
입력:
long long n = 28;

예상 출력:
std::vector<long long> expected = {5, 23};
입력:
long n = 28;

예상 출력:
long[] expected = new long[] {5, 23};

설명

28 − 2 = 26과 28 − 3 = 25는 소수가 아니지만 28 − 5 = 23은 소수이므로 답은 [5, 23]입니다.

예시 2
입력:
n = 4

예상 출력:
expected = [2, 2]
입력:
long long n = 4;

예상 출력:
std::vector<long long> expected = {2, 2};
입력:
long n = 4;

예상 출력:
long[] expected = new long[] {2, 2};

설명

2 + 2밖에 방법이 없으므로 답은 [2, 2]입니다.

접근 방법

먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.

힌트 1

p = 2, 3, 4, ... 순서로 시도해서 p와 n − p가 모두 소수인 첫 p에서 멈추세요.

힌트 2

소수 판별은 제곱근까지만 나누어 보면 됩니다.

힌트 3

가장 작은 p에서 멈추므로 p ≤ n − p는 저절로 만족됩니다.

예상 복잡도

시도한 후보 수가 k일 때 시간 O(k √n), 추가 공간 O(1)

참고 자료

이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.

코더마다 가장 좋은 통과 풀이입니다. 더 빠르고, 메모리를 덜 쓰고, 평가가 좋은 풀이가 위에 옵니다.

아직 통과한 풀이가 없습니다. 풀어서 1위를 차지하세요.

다른 사람의 풀이 보기

커뮤니티 솔루션

아직 공개된 풀이가 없습니다. 문제를 풀고 첫 풀이를 공유하세요.