백준 4948번 파이썬 문제풀이(기본수학2 - 베르트랑 공준) - 시간초과 해결

 

시간초과 코드

import math

while True:
    n = int(input())
    if n == 0: #0이면 반복문 탈출
        break
    array1 = [True for _ in range(2 * n + 1)] #소수 판별을 위한 리스트설정(True면 소수)
    array1[0], array1[1] = False, False #0,1은 소수가 아니기에 False로 설정

    # 에라토스테네스의 체 공식
    for i in range(2, int(math.sqrt(2 * n) + 1)): #2부터 int(math.sqrt(2 * n) 까지 돈다.
        if array1[i]: #만약 array1[i]가 소수라면
            j = 2 #i에 곱해줄 j값을 2부터 설정
            while i * j <= 2 * n: #i * j 가 2*n 보다 작거나 같다면
                array1[i * j] = False #해당 i*j의 값은 소수가 아니므로 False로 설정
                j += 1 #j를 1씩 증가

    count = 0 #개수 출력을 위한 count값 설정
    # 개수 출력
    for i in range(n+1, 2 * n + 1): #n+1(n보다 커야하기 때문) 부터 2 * n + 1 까지 설정
        if array1[i]: #만약 해당 i가 True(소수) 라면
            count += 1 #count값에다 +1
    print(count) #count 값 출력

-> 에라토스테네스의 체로 다음과 같이 코드를 짰다. 하지만 계속해서 시간초과가 떴다. 그이유는 무엇일까? 보면 반복문을 while문을 계속해서 돌때마다 2부터 int(math.sqrt(2 * n) +1) 돈다. 따라서 시간을 단축시키기 위해서는 while문 내부에서 소수판별을 위한 에라토스테네스의 공식을 계속해서 돌것이 아니라 미리 소수를 판별하는 것이 포인트이다. 개선된 코드는 다음과 같다.

 

import math

m = 123456 # 문제에서 제공한 m의 범위의 최댓값

array1 = [True for _ in range(2 * m + 1)] #소수 판별을 위한 리스트설정(True면 소수)
array1[0], array1[1] = False, False #0,1은 소수가 아니기에 False로 설정

# 에라토스테네스의 체 공식
for i in range(2, int(math.sqrt(2 * m) + 1)): #2부터 int(math.sqrt(2 * 123456) 까지 돈다.
    if array1[i]: #만약 array1[i]가 True(소수)라면
        j = 2 #i에 곱해줄 j값을 2부터 설정
        while i * j <= 2 * m: #i * j 가 2* 123456 보다 작거나 같다면
            array1[i * j] = False #해당 i*j의 값은 소수가 아니므로 False로 설정
            j += 1 #j를 1씩 증가

while True:
    n = int(input())
    if n == 0: #0이면 반복문 탈출
        break

    count = 0
    # 개수 출력
    for i in range(n+1, 2 * n + 1): #n+1(n보다 커야하기 때문) 부터 2 * n + 1 까지 설정
        if array1[i]:  #만약 해당 i가 True(소수) 라면
            count += 1 #count값에다 +1
    print(count)  #count 값 출력

-> 미리 123456까지 소수와 소수아닌 것을 True, False 값으로 에라토스테네스의 체 공식으로 구해놓는다. 그 후 while문을 돌면서 입력한 값의 *2 범위 내에서 소수가 몇개 있는지를 출력만 하면 시간초과 판정이 뜨지 않는다.