9020번 골드바흐의 추측

 

 

1) 사이트

9020번: 골드바흐의 추측

 

 

 

2) 문제

이 문제는 <에라토스테네스의 체 : 소수를 구하는 방법>과 <골드바흐의 수 / 골드바흐 파티션 : 홀수+홀수=소수>가 합쳐진 문제입니다.

특히 골드바흐 파티션 가운데 두 수의 차이가 작은 결과값을 내는 것이 포인트 입니다.

 

ex) 8 = <4+4>  / <3+5> 의 2가지 결과가 있지만 두 수의 차이값이 가장 작은 4 4를 출력하면 됩니다.

 

사실 처음 코드를 짤 때 조건문을 줄줄이 늘여놓아 복잡한 코드를 짰었는데, 그나마 다른 분들의 코드를 보며 공부하면서 줄일 수 있었습니다 ㅎ... 제가 참고한 사이트는 아래와 같습니다.

백준 9020 [파이썬] 골드바흐의 추측 : 차집합 연산 활용

 

 

 

3) 파이썬 코드

 

 

#prime을 판별하는 함수
def isPrime(n) : 
    for i in range(2, int(n**0.5)+1):
        if(n%i==0):
            return 0
    return n


#골드바흐의 추측 : 두 소수의 합으로 2보다 큰 짝수를 만들어 낼 수 있다.

#10000까지의 소수를 정리한다.
hundred=list(range(2,10001))
prime=[]

for n in hundred:
    result=isPrime(n)
    if(result!=0):
        prime.append(n)

    
test_case = int(input())

for i in range(0,test_case):
    number=int(input())
    half=number//2
    for j in range(half,1,-1):
        #두 수가 소수인지 체크한다.
        if (j in prime) and (number-j in prime):
            print(f'{j} {number-j}')
            break

 

 

 

 

3-1) 선수 지식

파이썬 코드를 이해하기 위해 알아야 할 선수 지식이 있습니다.

 

1) in의 사용법

>어떤 수 in 어떤 list

:즉, 어떤 리스트에 어떤 수가 존재하는지를 체크해주는 라이브러리 입니다.

 

2) 2~10000까지의 소수 리스트

: 수를 입력받고 소수를 일일히 찾아주는 것보다는

미리 소수 리스트를 만들어두고 사용하는 것이 <시간 초과>가 일어나지 않는 비결입니다.

 

3) 골드바흐의 수를 찾기 위해선 입력받은 수//2부터 1까지 역순으로 찾는 것이 빠릅니다.

:예를 들어 8을 생각하면 <3+5> / <4+4> / <5+3>의 수들을 도출해낼 수 있습니다.

만약 1부터 쭉 검사한다면, 이미 검토한 소수들까지 한 번더 검토하게 되고 <3+5 나 5+3이나 같은 결과>

8//2=4부터 역순으로 찾으면 단번에 수끼리의 차도 가장 작으면서 빠르게(절반만 검사하면 되기 떄문) 찾을 수 있어 코드 길이에도 좋은 영향을 미칩니다.

 

 

 

3-2) 설명

 

1. 2~10000까지의 소수를 구하는 리스트를 만듭니다.

 

 

#10000까지의 소수를 정리한다.
hundred=list(range(2,10001))
prime=[]

for n in hundred:
    result=isPrime(n)
    if(result!=0):
        prime.append(n)

 

 

hundred라는 리스트에 2~10000의 수가 들어가도록 합니다.

그 후 소수를 판별하는 함수를 통해 소수의 값만 받는 prime이라는 빈 리스트를 마련합니다.

 

그리고 hundred 각각 해당 함수에 넣어 prime에 소수만을 채워 2~10000까지의 소수 리스트를 만듭니다.

 

 

 

2. 소수 구하는 함수를 만듭니다 <에라토스테네스의 체>

 

 

#prime을 판별하는 함수
def isPrime(n) : 
    for i in range(2, int(n**0.5)+1):
        if(n%i==0):
            return 0
    return n

 

 

들어온 수를 <2 ~ 루트(들어온수)>로 나누었을 때 어떤 수로도 나눠지지 않는다면 그것은 소수입니다.

때문에 한 번이라도 나누어진다면 return 0을 하고, 아니면 해당 숫자를 반환해 prime 리스트에 append로 입력시키면 됩니다. (main에서)

 

 

 

3. 골드바흐의 수를 구하고 싶은 숫자를 입력 받고, <입력받은 수//2 ~ 1>역순으로 골드바흐의 수를 검토합니다.

 

 

for i in range(0,test_case):
    number=int(input())
    half=number//2
    for j in range(half,1,-1):
        #두 수가 소수인지 체크한다.
        if (j in prime) and (number-j in prime):
            print(f'{j} {number-j}')
            break

 

 

골드바흐의 수의 차가 작은 요소들부터 검사하므로 소수인 두 수를 발견하면 바로 출력하고 다음 수를 입력받으면 됩니다.

출력할 경우에는 작은 수부터 출력해야하는 것을 잊지마세요!

 

 

 

4) c언어

없음

 

---

궁금한 점이나 공유할 정보가 있다면 댓글로 남겨주세요 *^^*

끝!