(Python/🥈1)백준 알고리즘 9020번: 골드바흐의 추측

문제 출처:https://www.acmicpc.net/problem/9020

9020번: 골드바흐의 추측

잘못된 풀이:

array = list()
for i in range(2,10000):   
    count = 0

    for j in range(2,i):
        if i % j == 0:
            count += 1
            break
    if count == 0:
        array.append(i)

T=int(input())

for i in range(T):
    n = int(input())
    a = int(n//2)
    b = a
    while a>0:
        if array[a] and array[b] :
            break
        else:
            a -= 1
            b += 1

지금까지 푼 문제중에 가장오래걸렸다 2시간넘게는 쓴거같다..

 

2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것 

이러한 수를 골드바흐 수라고 한다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다

 

접근 방식은 만약 20 이라는 짝수를 받으면 1/2 을 한 수를 a,b두개로 만든다 10 10 으로 

두 수의 합이 20이 맞지만 소수가 아니기 때문에  a는 -1을 b는 +1 을 계속 해주면서 찾아준다.

 

이런 접근방식은 맞지만 중간 if문에 a와 b를 넣으면 0이 아닌이상 true 가 나오기 때문에 else문은 발동하지 않는다.

 

그래서 에라토스테네스의 체 를 사용해 false 와 true 로 이루어징 소수 리스트를 만들었다.

 

T=int(input())

array = [False,False] + [True] * 10000
for i in range(2,101):
    if array[i] == True:
        for j in range(i+i, 10001, i):		# 배수들 제거
            array[j] = False
for i in range(T):
    n = int(input())
    a = int(n//2)
    b = a
    while a>0:
        if array[a] and array[b] :
            # print(a,b)
            break
        else:
            a -= 1
            b += 1

 

숫자 0과 1은 false 즉 소수가 아니고 true 인 리스트 10000개를 만들어주고

각 숫자들의 배수들을 하나하나 지워나가면 결국 True는 소수만 남는다.