[파이썬] 백준 9020 : 골드바흐의 추측

[파이썬] 백준 9020 : 골드바흐의 추측

https://www.acmicpc.net/problem/9020

9020번: 골드바흐의 추측

실버 1

정수론, 소수 판정

---

접근

먼저 아리토스테네스의 체를 이용해 소수를 판정한다. 제곱근보다 작은 수 범위에서 합성수를 걸러내면 빠르게 소수를구할 수 있다.

소수중에서 x2를 한 값이 입력한 값을 넘는 경우부터 구한 소수를 역순으로 탐색하면서 두 소수의 합이 입력한 값과 같은 경우일 때를 출력하도록 했다.

 

다만 이 방법은 입력한 까지의 소수를 전부다 구해놓고 탐색을 하기 때문에 시간이 굉장히 오래 걸리는 방법이었다.

 

pypy3 코드

import sys; input = sys.stdin.readline
def prime(x):
    for i in range(2, int(x**0.5)+1):
        if x % i == 0:
            return False
    return True
T = int(input())
for _ in range(T):
    num = int(input())
    prime_lst = [2, 3]

    for i in range(4, num+1):
        if prime(i):
            prime_lst.append(i)
    flag = False
    for p in range(len(prime_lst)):
        if flag == True:
            break
        if prime_lst[p] * 2 == num:
            print(prime_lst[p], prime_lst[p])
            break
        elif prime_lst[p] * 2 > num:
            for i in range(p, 0, -1):
                if prime_lst[p] + prime_lst[i] == num:
                    print(prime_lst[i], prime_lst[p])
                    flag = True
                    break

 

다른 사람 코드 (Python3)

from sys import stdin

T=int(stdin.readline()) #1. 테스트 케이스 개수를 받는다 = T

def prime(number): #2. 소수를 판별하는 함수를 만든다
    if number<2:
        return "No"

    for j in range(2,int(number**0.5)+1):
        if number%j==0:
            return "No"

    return "Yes"

for i in range(T): 
    n=int(stdin.readline()) #3. 값을 입력받아 n으로 지정하고,

    a=int(n/2) #3. 반절 값을 시작으로 하나씩 줄여나갈 변수를 지정.
    b=int(n/2) #3. 반절 값을 시작으로 하나씩 늘여나갈 변수를 지정.

    for k in range(int(n/2)): #4. n 전체가 아닌 반절값만 증명하면 OK
        if prime(a)=="Yes" and prime(b)=="Yes": #4-1. a,b 둘다 소수일 경우 Yes 출력
            print(a,b)
            break
        else: #4-2. 아닐 경우 변수의 차이를 두어 확인
            a=a-1
            b=b+1

 

입력한 값의 절반 위치에서 시작하여 a를 감소, b를 증가시키면서 소수를 판별한다. 이 경우 두 수가 소수라면 문제의 조건을 바로 만족한다고 한다.