https://www.acmicpc.net/problem/14905
문제
모든 자연수를 4개의 소수의 합으로 나타낼 수 있을까? 이 물음에 대한 답은 '8 이상의 모든 자연수에 대해 그렇다'이지만, 데이빗은 그 사실을 알지 못했다. 데이빗은 프로그램을 돌려 4개의 소수의 합으로 표현할 수 없는 수를 찾아내 보기로 했다. 소수는 "두 개의 다른 자연수로만 나눠 떨어지는 자연수"이다. 예를 들어, 37은 37과 1로만 나눠 떨어지므로 소수이다
입력
입력 파일에는 한 줄에 하나씩 1 이상 100,000,000 이하의 자연수가 주어진다.
출력
입력 라인에 맞춰, 주어진 조건에 맞는 4개의 소수를 한 줄에 출력한다. 입력된 수가 소수 4개의 합으로 표현될 수 없으면 “Impossible.”이라 출력한다. 답은 여러 개가 있을 수 있다. 하지만 더해서 입력된 수가 나오는 소수 4개라면 모두 정답이다.
해결방안: 골드바흐의 추측을 이용하자. 8이상의 자연수일때 짝수이면 2 + 2+ A + B의 형태로 나타낼 수 있다.
예를 들어 14일때 2 + 2 + 5 + 5 (모두 소수) or 2 + 2 + 3 + 7(모두 소수) 이런식으로 2 + 2 + 소수 + 소수의 형태로 8이상의 짝수를 모두 표현 할 수 있다.
그리고 홀수 일때는 2 + 3 + 소수 + 소수의 형태로 표현 가능하다.
예를 들어 15일때 2 + 3 + 5 + 5(모두 소수)이런식으로 짝수,홀수를 분기로 나눠서 계산하면 된다.
그리고 에라토스테네스의 체를 통해 1차적으로 소수를 판별해준다.
전체 소스 코드->
'알고리즘' 카테고리의 다른 글
백준 14921 C언어 (0) | 2022.02.25 |
---|---|
백준 1316 C언어 (0) | 2022.02.23 |
백준 1475 C언어 (0) | 2022.02.19 |
백준 1448 C언어 (0) | 2022.02.17 |
분할정복 (0) | 2022.02.15 |