꾸준히 개발하기

소수 판별 알고리즘 중 에라토스테네스의 체 방식을 알고 있어야 시간 초과가 안 나는 문제다. 물론 나는 에라토스테네스의 체 방식을 매번 입력받을 때마다 하고 반복문도 많이 써서 시간초과만 우다다 받았다 ^^ 

시간초과를 막는 중요한 포인트가 2개였다...

1. 에라토스테네스의 체를 범위 내의 모든 숫자에 한해서 1번만 돌리기
2. 최대한 반복문 줄이기

최대 입력 가능한 숫자 범위가 1000000이니까 그 안을 일단 다 소수를 판별해버린다! 가능한 소수를 미리 다 계산한 뒤 또 범위 내에서 새로운 리스트를 만들지 말고, 반복문 안에서 True, False값을 체크해서 보기만 해야 시간 초과가 안 난다.

시간초과가 이렇게 머리를 아프게 하는지 간만에 느껴본 문제...^^ 같은 골드바흐 문제는 꽤 금방 시간초과를 잡아서 기가 살아있었는데 1시간 내내 계속 시간 줄이다 보니까 기가 쪼그라들었다... 그래도 풀긴 푼거니까... 어디서 시간초과가 나는지 잘 살펴보는 능력도 정말 중요하구나, 또 느낀다.

파이썬 코드는 다음과 같다.

erato = [True] * 1000001
erato[0], erato[1] = False, False
for i in range(2, 1001):
    if erato[i]:
        for j in range(i + i, 1000001, i):
            erato[j] = False

while True:
    n = int(input())
    wrongFlag = True
    if n == 0:
        break

    for i in range(3, n):
        if erato[i] == True:
            if erato[n - i] == True:
                wrongFlag = False
                print(n, "=", i, "+", n - i)
                break
    if wrongFlag:
        print("Goldbach's conjecture is wrong.")

눈물의 코드... (쓸 필요도 없었고 시간초과만 유발했던 녀석들이다)

# n 미만의 수 중 홀수인 소수 리스트 리턴
def getPrimeNums(n):
    return [i for i in range(n) if erato[i] == True and i % 2 != 0]


def getGoldB(target, nums):
    middleIdx = -1
    for i in range(len(nums)):
        if nums[i] > int(target / 2):
            break
        middleIdx = i

    for i in range(middleIdx + 1):
        for j in range(len(nums) - 1, middleIdx, -1):
            if nums[i] + nums[j] < target:
                break
            if nums[i] + nums[j] == target:
                return [nums[i], nums[j]]
    return False

나름 시간 좀 줄여보겠다고 다른 골드바흐 문제에서 시간초과 잡아줬던, 중간값 구해서 어찌저찌 해봤는데 역시나 시간초과였다. 그냥 T/F 값 판단해서 바로바로 계산하는게 제일 빠르구만