[Python] 백준 6588 골드바흐의 추측

코드 작성

def pr(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n%i == 0:
            return False
    else:
        return True
import sys
while True:
    n = int(sys.stdin.readline())
    if n == 0:
        break
    for i in range(2,n):
        if pr(i) and pr(n-i):
            print(f'{n} = {i} + {n-i}')
            break

코드  풀이

#0. 문제풀이

(1) 소수를 검출하는 함수를 정의한다.

(2) for문을 이용하여 n값에 대해서 i증가하고, n-i는 점점 감소하면서 숫자를 찾는다.

 

#1. 소수검출(에라토스테네스의 체)

n값이 소수(prime number)인지 판별하는 함수이다.

n값이 1일 경우 소수가 아니므로 False

2부터 n의 제곱근까지의 값 중에서 i로 나누어 떨어지는 수는 제외

★ int(n**0.5)+1은 숫자 n에 대한 제급근의 배수를 모두 제거하면 소수

예를 들어 17까지의 수 중 제곱근은 4이며, 2,3,4의배수를 제거한 나머지 값은 소수이다.

2의 배수인 4, 6, 8, 10, 12, 14, 16

3의 배수인 3, 6, 9, 12, 15

4의 배수는 2의 배수에 포함

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17

 

#2. while문

while의 무한루프를 이용하는데

(1) n값을 입력하고

(2) n값이 0이면 break

(3) 그렇지 않으면 for를 이용하여 i는 증가하면서 n-i는 감소하는 값 중에서 소수의 값을 찾는다.

(4) f스트링을 이용하여 변수의 값을 출력한다.