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

코드 작성

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
n = int(input()) 
for i in range(n):
    num = int(sys.stdin.readline())
    a = num//2
    b = num//2
    while True :
        if pr(a) and pr(b):
            print(a,b)
            break
        else:
            a-=1
            b+=1

코드  풀이

#0 문제순서

(1) 에라토스테네스의 체를 이용하여 함수 만들기

(2) 입력값 num을 2로 나눈 중간값 a,b에서 a는 1씩 감소하는 값, b는 1씩 증가하는 값 모두 소수가 되는 조건까지 while문 돌리기

 

#1. 에라토스테네스의 체

소수를 검출하는 함수 def pr(n)을 정의하는데 에라토스테네스의 체를 이용하여 작성한다. 만약 n이 1이면 소수가 아니므로 False, 2부터 계산을 하는데 i로 나눈 값이 0으로 나누어 떨어지면 False, 그렇지 않으면 소수이다.

★ 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

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

#2.

문제에서 두 소수 값의 차이가 적은것을 나타내라고 했으므로 num의 중간값인 (num/2)를 각각 a,b로 정하고 소수가 아닐 경우 a는 1씩 감소, b는 1씩 증가하는 값을 적는다. 소수를 찾았을 경우 그 수를 프린트 하고 while을 종료한다.

import sys
n = int(input()) 
for i in range(n):
    num = int(sys.stdin.readline())
    a = num//2
    b = num//2
    while True :
        if pr(a) and pr(b):
            print(a,b)
            break
        else:
            a-=1
            b+=1