목록골드바흐의 추측 (1)
블로그 옮겼습니다
BOJ 1153번 네개의 소수
문제 링크 \( N\le{10^6}\)자연수 N이 주어진다. N을 네개의 소수의 합으로 분리할 수 있으면 그 네개의 수를 출력하고불가능하면 -1을 출력하는 문제이다. 우선 골드바흐의 추측이라는 것이 있다. 2보다 큰 짝수는 무조건 두개의 소수의 합으로 나타낼 수 있다는 것이다.내가 알기론 이미 꽤 큰 수(적어도 PS에서 주어지는 입력의 범위보단 큰 수) 까지는컴퓨터로 일일이 돌려보아 증명이 되었다고 알고있다. 그러니까 맞다고 생각하고 풀면된다 ㅎㅎ일단 입력으로 주어진 N이 홀수일 때와 짝수일 때로 나누어 보자.만약 홀수라면 골드바흐의 추측을 적용하기 위해 이를 짝수로 만들어 줘야 하므로 우선 하나의 수를 빼야하는데너무 많이 빼면 2이하가 될 수도 있으므로 가장 적게 빼는게 최선이므로 가장 작은 홀수 소수..
Algorithm/Problem Solving
2017. 8. 23. 21:05