네 개의 소수1 [백준 / BOJ] 네 개의 소수 - 1153 (Java) 문제 : https://www.acmicpc.net/problem/1153 임의의 자연수 N에 대해서, 해당 수를 4개 소수의 합으로 표현하는 문제이다.4개의 소수 중, 중복인 수가 있을 수 있으며, 답이 여러가지인 경우가 있을 수 있다, 그 중 하나만 출력하면 된다. 풀이1. 문제의 4개의 소수를 'N을 구성하는 수'라고 하자. N을 구성하는 수는 모두 소수이므로, 우리는 자연수 중 어떤 수가 소수인지 알아야한다. 주어지는 N의 범위가 크기 때문에 에라토스테네스의 체를 이용해 N이하의 자연수 범위에서의 소수 여부를 저장하는 테이블을 구하자. 2. 문제에서 의도한 정석적인 풀이는 아닐 수 있지만, 필자는 골드바흐의 추측을 이용해 해결하였다. 골드바흐의 추측이란, '4이상의 모든 짝수는 두 소수의 합.. 2025. 1. 24. 이전 1 다음
