백준 9020 골드바흐의 추측 - python

출력:

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

9020번: 골드바흐의 추측

풀이:

<내풀이>

def prime_list(n):
    prime = [True] * (n+1)
    
    m = int(n**0.5)
    if n <= 3:
        prime[0] = False   # f t t t
        return [i+1 for i in range(n) if prime[i]==True ]
    else:
        for i in range(2,m+1):
            if prime[i] == True:
                for j in range(i+i,n+1,i):
                    prime[j]=False
        return [i for i in range(2,n+1) if prime[i]==True]  
            
t = int(input())

for _ in range(t):
    a = int(input())
    b = prime_list(a)
    hubo = []
    d = []
    for i in b:
        for j in b:
            if i+j == a:
                if i <= j :
                    hubo.append([i,j])
                    d.append(j-i)
    ans = hubo[d.index(min(d))]
    print(ans[0], ans[1])

<다른 사람풀이>

prime_list = [False, False] + [True]*10002

for i in range(2,10002):
    if prime_list[i]:
        for j in range(i+i,10002,i):
            prime_list[j] = False
            
T = int(input())

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

 

내가 이전에 계속 쓰던 리스트로 풀어서 밑과정에서 아무리 과정을 줄여도 출력되지가 않았다. 여기에는 올리지 못하고 지워버렸지만 긴시간 계속 다양하게 해봤는데 실패해서.. 결국 다른 답을 참고해서 수정했다.

 

1. 일단 0 1은 소수가 아니니까 False 로 만들어놓고 이 문제에서 제안한 수 보다 조금 더 많게 True 리스트를 만들어놓는다.

그 다음 에라토스테네스의 체를 이용해서 첫 소수의 배수들은 다 False로 바꿔준다.

 

2. 그 다음은 입출력을 받아주고

 

3. 이 과정이 좀 중요하다. 입력값에 답을 구하려면 입력값을 절반으로 나눠준 뒤에 두 개로 나뉜 값에 각각 -1 +1 을 더해주면 그 둘의 합은 어차피 입력값이 된다. ( a / 2.  a/ 2.     ->  a/2-1, a/2 +1   -> 결국은 합이 a 

 

4. 위와 같은 방식으로 진행할것이고 여기서 반으로 나누고 -1, +1 을 하면서 그 수가 소수가 된다면 그 값은 문제의 답일 것이다.

그래서 while 문에서 두 수가 소수라면 출력하고 멈추고 그것이 아니라면 a는 -1 b는 +1 을 더해준다.