골드바흐의 추측
골드바흐 파티션_ 백준 17103
골드바흐 파티션은 이전에 풀었던 골드바흐의 추측과 관련된 문제입니다. 2020/05/17 - [백준 문제풀이] - 골드바흐의 추측 _ 백준 6588 골드바흐의 추측은 2보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다. 라는 추측이다. 이번 문제는 이 골드바흐의 추측을 기반으로 짝수 N을 두 소수의 합으로 나타내는 골드바흐 파티션을 구하는 문제이다. 여기서 두 소수의 순서만 다른 것은, 같은 파티션으로 취급한다. 에라토스테네스의 체를 활용하여 소수를 먼저 확인해놓고, 그 뒤에 결과값을 출력하는 형식으로 알고리즘을 짜면 된다. 골드바흐 파티션을 계산할 때, '두 소수의 순서만 다른 것은, 같은 파티션으로 취급한다.'라는 조건에 따라 해당 값을 반으로 나눈 값까지만 세면 된다. 코드는 다음과 같다..
골드바흐의 추측 _ 백준 6588
이번에는 소수와 관련되어서, 조금 더 심화된 내용인 골드바흐의 추측과 관련된 문제입니다. 골드바흐의 추측은 문제에 나온대로, "4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다." 를 중심으로 이루어지는데요, 앞서서 풀었던 문제인 소수 찾기, 구하기의 알고리즘이 다시 활용됩니다. - 해당 코드는 아래 링크에. 2020/05/16 - [백준 문제풀이] - 소수 찾기 / 소수 구하기 _ 백준 1978,1929 소수 찾기 / 소수 구하기 _ 백준 1978,1929 1978번, 1929번 문제는 소수와 관련된 문제이다. 어떤 수 N이 소수가 아니라면, N = a * b 라고 표현할 수 있는데, 이떄 a와 b의 차이가 가장 적은 경우는 √n 이다. 그러므로, 검사를 n까지만 해서, 소수 runa-na..