[백준 9020번 python] 골드 바흐의 추측

정답 코드

li=[0]*10001
for num in range(2,10001):
    for i in range(2,int(num**0.5)+1):
        if num % i == 0:
            li[num] = 0
            break
    else:
        li[num]=num
for _ in range(int(input())):
    n = int(input())
    st = 0
    for i in range(n//2,0,-1):
        if li[i] != 0:
            st = i
            break
    sosu_list = sorted(set(li[:n+1]))
    st_idx=sosu_list.index(st)
    brk=False
    for idx,i in enumerate(sosu_list[st_idx::-1]):
        for j in sosu_list[idx:]:
            if i+j == n:
                print(min(i,j),max(i,j))
                brk = True
                break
            if i+ j > n:
                break
        if brk:
            break

내 풀이의 중요 발상

1. 소수가 아니면 0 맞다면 그 숫자를 넣어서 리스트의 인덱스가 곧 그 숫자다.

2. set을 통해 중복되는 0을 없애준다.

3. 주어진 값의 중앙에서 가장 가까운 값(소수)을 찾아 시작 값으로 지정한다.(작은 쪽으로)

4. 이중 for문으로 바깥 for문의 시작은 3번의 숫자로부터 내림차순, 안쪽은 바깥 for문의 값에서 오름차순으로 진행하여 합이 같을 때 출력!

5. 이중 for문의 두 개의 값의 합이 주어진 값보다 크다면 안쪽 for문을 중지한다.

 

시행착오

- 소수 리스트의 중간 값을 구하는 과정에서 중간 값이 리스트의 중간 값일 거라는 착각

li = [0] * 10001
for num in range(2,10001):
    for i in range(2,int(num**0.5)+1):
        if num % i == 0:
            li[num] = 0
            break
    else:
        li[num] = num
for _ in range(int(input())):
    n = int(input())
    sosu_list = list(sorted(set(li[:n+1])))[1:] #0번인덱스는 0이기때문
    print(sosu_list, len(sosu_list), sosu_list[len(sosu_list)//2])
    brk = False
    for idx,i in enumerate(sosu_list[len(sosu_list)//2::-1]):
        for j in sosu_list[idx:]:
            if i+j == n:
                print(min(i,j),max(i,j))
                brk = True
                break
        if brk:
            break

반례 : n = 1000일 때 431 569 출력, 정답 491 509

배울 다른 풀이

sosu = [0 for i in range(10001)]
sosu[1] = 1
for i in range(2, 98):
    for j in range(i * 2, 10001, i):
        sosu[j] = 1
t = int(input())
for i in range(t):
    a = int(input())
    b = a // 2
    for j in range(b, 1, -1):
        if sosu[a - j] == 0 and sosu[j] == 0:
            print(j, a - j)
            break
#https://pacific-ocean.tistory.com/129

1. 에라토스테네스의 체로 소수 판별

2. 작은 소수부터 출력을 해야 하기에 a에 2를 나눈 몫부터 시작

3. a에 소수를 빼주었을 때 빼준 값도 소수라면 그 두 소수가 정답

def is_prime(n):
    if n == 1:
        return False
    for j in range(2, int(n**0.5) + 1):
        if n % j == 0:
            return False
    return True


for _ in range(int(input())):
    num = int(input())

    a, b = num//2, num//2
    while a > 0:
        if is_prime(a) and is_prime(b):
            print(a, b)
            break
        else:
            a -= 1
            b += 1
            
#https://velog.io/@jieuihong/%EB%B0%B1%EC%A4%80-9020-%EA%B3%A8%EB%93%9C%EB%B0%94%ED%9D%90%EC%9D%98-%EC%B6%94%EC%B8%A1%EC%8B%A4%EB%B2%841-Python

1. 소수 판별 함수를 만들고

2. a와 b는 중간 값을 시작

3. a는 1 감소 b는 1 증가하며 둘 다 소수면 출력

배운 점

1. 에라토스테네스의 체

def prime_list(n):
    # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
    sieve = [True] * n

    # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i] == True:           # i가 소수인 경우
            for j in range(i+i, n, i): # i이후 i의 배수들을 False 판정
                sieve[j] = False

    # 소수 목록 산출
    return [i for i in range(2, n) if sieve[i] == True]

1. n의 최대 약수가 sqrt(n) 이하이므로 int(sqrt(n))까지 검사

2. i가 소수라면 배수들은 모두 false처리(step을 i로 지정)

 

2. 발상

첫 번째 다른 정답 코드에서 하나의 값을 지정하고 그 값을 주어진 값에 빼주었을 때, 그 수도 소수라면 정답이라는 발상이 좋았고

그로 인해 두 번째 정답의 코드도 쉽게 이해가 갔다.

 

 

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4