[기초-소수] ★★백준 9020번 골드바흐의 추측 with Python3

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

문제

 

내 풀이

import math
import sys
n = 10000
a = int(math.sqrt(n))

primelist = []
for i in range(2, n-1):
    primelist.append(i)

primeN = []
for i in range(2, a):
    primeN.append(i)

for i in range(4, a):
    for j in range(2, i):
        if i % j == 0 and i in primeN:
            primeN.remove(i)

power = 0
for j in range(len(primeN)):
    power = primeN[j]
    for i in range(2, n):
        c = power*i
        if c in primelist:
            primelist.remove(c)
        elif c > n:
            break

# 리스트안에서 근사값을 찾는 함수 https://blog.naver.com/PostView.nhn?blogId=zzang9ha&logNo=222010163074


def findNearNum(primelist, values):
    answer = [0 for _ in range(2)]  # answer 리스트 0으로 초기화

    minValue = min(primelist, key=lambda x: abs(x-values))
    minIndex = primelist.index(minValue)
    answer[0] = minIndex
    answer[1] = minValue

    return answer


n = int(input())


for _ in range(n):
    goldbach = []
    givenNo = int(input())
    # print(givenNo)
    first = 0
    second = 0
    nearNum = []
    values = givenNo/2
    nearNum = findNearNum(primelist, values)
    # print(nearNum)
    if nearNum[1] == 2:
        print('2 2')
    else:
        for i in range(int(nearNum[0])):
            first = primelist[int(nearNum[0]) - i]
            for j in range(int(len(primelist) - nearNum[0])):
                second = primelist[int(nearNum[0]) + j]
                result = first + second
                if result == givenNo:
                    goldbach.append(f'{first} {second}')
                    break
            if len(goldbach) == 1:
                break
        print(goldbach[0])

해설

진짜 오지게 틀려먹었었다. 이건 정신 건강상 정답풀이를 보자. 

시간문제부터, range 지정까지 하나두개 문제 있던게 아니다.

 

정답 풀이

# 소수 집합 만들기
nums = {x for x in range(2, 10_001) if x == 2 or x % 2 == 1}
# nums = 2와 홀수로 이루어진 집합
for odd in range(3, 101, 2): # 101 == int(math.sqrt(10_000)) + 1
    nums -= {i for i in range(2 * odd, 10_001, odd) if i in nums}
    # 홀수의 배수로 이루어진 집합을 빼줌

# 골드바흐 수를 출력
t = int(input())
for _ in range(t):
    even = int(input())
    half = even//2  # 입력받은 짝수를 2로 나눈 몫을 구함. / 기호를 쓰면 실수가 됨.
    for x in range(half, 1, -1):  # 차이가 적은 두 수를 구하기 위해서 큰수부터 꺼냄
        if (even-x in nums) and (x in nums):  # even-x 와 x가 소수 집합에 포함 되었는지 확인
            print(x, even-x)  # 작은수부터 출력
            break

출처:https://ooyoung.tistory.com/100

해석

https://greendreamtrre.tistory.com/24

range함수의 독특한 사용. half가 무조건 1보단 클텐데 역순으로 x값을 준단 말인가?

놀랍게도 등차가 - 일 경우 그렇다!

 

이경우 아래와 다르게 , even-x 를 통해 x와 even-x 가 골드바흐의 수가 성립되는 소수인지를 검증한다. 

 

{i for i in range(2 * odd, 10_001, odd) if i in nums} 

신기한 방법이다.

i를 매 for 마다 리턴하는것같다. 

 

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

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

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

출처:https://deokkk9.tistory.com/20

해석

두번째꺼가 더 이해 되는듯. 하지만 골드바흐의 수를 찾는 logic이 이상하게 느껴진다.

1. prime_list라는 첫두개는 false , 나머지는 전부 true인 list를 만든다.

2. for i in range(2,10002) 첫 두개를 제외하고,

3. if prime_list[i]가 

4. for j in range(2*i, 10002, i ): 

2*i 번쨰 부터 i 간격으로 ( ni | n =1,2,3...) 스캔 :

즉, 현 index에 해당하는 숫자의 모든 n 곱 (제곱아님) 들을 false로 바꿔버리는 함수. 

에라토스테네스의 체일경우 소수들의 제곱으로 해결하기에 더 빠르겠지만, 조금은 비효율적이더라도 소수들을 걸러낼 수 있다. 

 

 

5. if prime_list[a] and prime_list[b]: 

if문 다음에는 조건이 들어가야하는데 and 연산자는 양쪽 모두 참일 때이다.

n을 나눈 수가 a, b인데 prime_list[a] or b는 false 값일 것이다. 그렇기에 else로 넘어가고 위아래로 index를 증가시킨다.

 

 

 

하지만 여러 문제가 느껴지는데 왜 이게 맞는 코드일까?

 

1.  prime_list[a] ,b 는 그 합이 n이어야 골드바흐 수이다. 하지만 여기에는 그런 조건이 빠졌다. 그저 중간에서 가장 가까운 양쪽 소수를 찾았을때 멈추게 되어있다.

2. index는 1씩 증가/감소한다. 둘의 index 간격이 일정하다는건데. 골드바흐의 수가 소수 풀에서 같은 index 거리에 존재하리란 보장이 없다.

 

하지만 내가 이해 못한 부분이 있나 보다.