백준 9020 - 골드바흐의 추측

소수 관련 문제

풀이과정

1. 소수 리스트를 만든다.

2. input값의 절반에 가장 가까운 작거나 같은 소수(a)를 찾고 소수 리스트에서 a의 index값을 찾는다.

3. a와 더해서 input값이 되는 또 다른 소수(b)를 찾는다.

4. 만약 조건에 맞는 b가 없다면 a보다 인덱스가 하나 작은 소수를 찾는다.

5. 3-4를 조건에 맞는 a, b를 찾을 때 까지 반복한다.

코드

#에라토스테네스의 체를 만들기 위한 리스트 생성
tlst = [False, False] + [True]*(10000-1)
#소수를 저장할 리스트 생성
plst = []

for i in range(2, int(101)):
#101은 10000에 루트를 씌운 값(100) + 1 (range함수는 이하부터 미만이므로 +1을 해줘야함)
    if tlst[i] == True:
        j = 2
        while i*j <= 10000:
            tlst[i*j] = False
            j += 1
            #소수 i의 배수들을 False로 초기화
for i in range(len(tlst)):
    if tlst[i] == True:
        plst.append(i)
        #소수를 plst에 저장
    

def Gold_vach(num):
    idx = max([i for i in range(len(plst)) if plst[i] <= num//2])
    #plst중 num/2에 가장 가까우면서 작거나 같은 수의 인덱스를 idx에 초기화
    for i in range(idx, -1, -1):
    #idx에서 출발해서 점점 작아지다가 0까지 조회
        for j in range(i, len(plst)-1):
        #idx에서 출발해서 점점 커지다가 최대값까지 조회
            if plst[i] + plst[j] == num:
                return plst[i], plst[j]
            elif plst[i] + plst[j] > num:
                break
                #합이 num보다 커지면 빠르게 반환

T = int(input())
for case in range(T):
    N = int(input())
    a, b = Gold_vach(N)
    print(a,b)

생각해볼점

처음 문제를 풀 때, 테스트 케이스 하나마다 소수리스트(plst)를 새로 만들어 줬더니 시간이 매우 오래 걸렸다.

이후 처음부터 소수리스트를 만든다음 테스트 케이스마다 소수 리스트를 사용하도록 바꿔주었더니 속도가 7배정도 증가한 것을 확인 하였다.

시간이 짧은 사람들의 풀이를 본 결과, 굳이 소수를 저장하는 리스트(plst)를 따로 생성하지 않고 미리 생성해둔 리스트(tlst)를 사용해서 푸는 것을 확인 하였다. 이런 방식을 이용한다면 tlst의 True인 값을 가진 index를 수로 이용하여 풀 수 있다. 하지만 현재 나의 실력으로 구현하기에는 오랜 시간이 걸릴 것 같아 공부가 진전된 뒤에 다시 보기로 했다.