백준 4938번 파이썬

1. 문제

2. 설명

역시나 while문 안에 for문을 넣으면 타임아웃이 뜬다. 아직까지 시간복잡도를 생각하며 코딩하는 것은 좀 어렵다 .

시간초과가 안뜨게 하기 위해 미리 소수를 판별하는 함수를 만든다.

문제에서 n이 2부터 123,456까지라고 주어져있으므로, 2부터 246,912(123,456 * 2)까지의 리스트를 만든다.

for문으로 리스트 안에 있는 숫자들이 소수인지를 미리 걸러준 후 새로운 배열에 넣어준다.

3. 코드

정답 코드

import math

def IsPrime(num):
    a = int(math.sqrt(num))
    if num == 1:
        return False
    else:
        for i in range(2, a+1):
            if num % i == 0: 
                return False
        return True

Num_list = list(range(2,246912))
Sort_list = []
for i in Num_list:
    if IsPrime(i):
         Sort_list.append(i)

while True:
    n = int(input())
    if n == 0:
        break
    cnt = 0
    for i in Sort_list:
        if n < i <= n*2:
            cnt += 1
    print(cnt)

처음 적은 코드

from math import sqrt

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

    cnt = 0

    for i in range(n+1, 2*n+1):
        if i == 1:
            continue
        elif i == 2:
            cnt += 1
            continue
        else:
            for j in range(2, int(sqrt(i)+1)):
                if i % j == 0:
                    break
            else:
                cnt += 1

    print(cnt)

---

시간복잡도 때문에 시간을 꽤 쏟은 문제..

결국 계속 시간초과가 떠서 답을 보고 이해하게 되었다 ㅠㅠ