7113 : 소수 쌍
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
골드바흐의 추측(Goldbach's conjecture)에 따르면 4 이상의 모든 짝수는 두 소수의 합으로 나타낼 수 있습니다.
4 이상의 짝수 n이 주어질 때,
4 이상의 짝수 n이 주어질 때,
n = p + q (단, p ≤ q 인 소수)를 만족하는 소수 쌍 중 p가 최소인 쌍을 구하십시오.입력 설명
첫째 줄에 짝수 $n$이 주어집니다. ($4 \le n \le 1{,}000{,}000$)
출력 설명
합이 $이 되는 두 소수 , q$ ( \le q$) 중 $가 가장 작은 쌍을 공백으로 구분하여 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
10
출력 예시
COPY
복사되었습니다!
복사되었습니다!
3 7도움
에라토스테네스의 체로 1,000,000 이하의 소수를 전처리한 뒤, p를 2부터 n//2까지 키워가며
p와 n-p가 모두 소수인 경우를 탐색하여 출력합니다.