💡백준 9020
◽ 문제
◽ 입력 & 출력
◽ 풀이
-
2보다 큰 모든 짝수는 두 소수의 합 으로 나타낼 수 있다는 것이다. 이러한 수를 골드바흐 수라고 한다.
-
짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션 이라고 한다.
ex)
4 = 2 + 2
6 = 3 + 3
8 = 3 + 5
10 = 5 + 5
12 = 5 + 7
14 = 3 + 11
14 = 7 + 7
-
2보다 큰 짝수 n이 주어졌을 때, n의 골드바흐 파티션을 출력하는 프로그램을 작성하는 문제이다
-
단 만약 가능한 n의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력한다.
-
소수를 구하기 위해 함수를 구현했다.
-
먼저 1은 소수가 아니기 때문에 1을 제외시켜주고, 2~ sqrt(num)+1만큼 범위를 지정해준다.
-
나머지가 0이면 소수가 아니기에
제외시킨다 -
1보다 크고 나머지가 0이 아닌
즉 1과 자기 자신만을 약수로 가지는 수(소수)
-
15번째 줄: 테스트 케이스의 개수 T를 입력받는다.
-
t와 같이 하나만 입력받는 경우는 int(input())만 써도 되지만
여러줄 일때는 int(sys.stdin.readline()) 입력시간을 줄여주는 것이 좋다. -
17,18번째 줄: t만큼 반복문을 돌고, 소수를 구할 짝수even를 입력받는다.
-
19번째 줄: 중간값으로 쪼개기 위해 2로 나누고 몫을 각 a,b에 저장한다.
또한 중간값으로 나누면 차이가 가장 적은 두개의 수로 나눠지기 때문이다.
-
21번째 줄: 먼저 밑에서 a를 계속 차감시킬것이기 때문에 a가 0보다 클때만 반복을 하도록 지정했다.
-
22~24번째 줄: 반으로 쪼갠 a와b를 check_prime()에 넣어 소수인지 판단 하고, and연산으로 두 개가 전부 만족할 때 출력한다.
-
eles: 중간값으로 나눠준 a,b가
모두 소수가 아니면a = a-1 , b = b+1 해서 두 수가 모두 소수인지 확인 한다.예제 입력대로 입력해보면
짝수 8 ➡️ 4 , 4로 나눠진다. ➡️ 둘다 소수가아니기때문에
a-=1 b+=1 해서 다시 소수인지 확인한다.
짝수 10 ➡️ 5 , 5로 나눠진다. ➡️ 둘다 소수!
짝수 16 ➡️ 8 , 8로 나눠진다. ➡️ 둘다 소수가아니기때문에
a-=1 b+=1 해서 다시 소수인지 확인한다.
8 , 8 ➡️ 7, 9 = 9가 소수X
7 , 9 ➡️ 6, 10 = 둘다 소수X
6 , 10 ➡️ 5, 11 = 둘다 소수!
✅전체 코드
