목록2025/05/23 (1)

넘치게 채우기

[BOJ] 1152 - 네 개의 소수

https://www.acmicpc.net/problem/1153BOJ - 네 개의 소수문제 유형: 수학, 정수론, 소수 판별, 에라토스테네스의 체문제 난이도: Gold III시간 제한: 2초메모리 제한: 128MB 문제임의의 자연수가 주어지면, 이를 네 개의 소수의 합으로 분해하는 프로그램을 작성하시오. 예를 들어 38 = 5 + 7 + 13 + 13이 된다. 입력첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 출력첫째 줄에 네 개의 소수를 빈 칸을 사이에 두고 순서대로 출력한다. 불가능한 경우는 -1을 출력한다. 풀이우선, 에라토스테네스의 체를 이용해서 소수들을 걸러준다. 골드바흐 추측으로 풀 수 있다고 한다. 골드바흐 추측은 2보다 큰 모든 짝수는 두 소수의 합으로 표현될 수 있..
PS/BOJ 2025. 5. 23. 18:54
이전 Prev 1 Next 다음