18_1929_소수 구하기.md

앞서 베르트랑 공준 문제에서

사용한 에라토스테네스의 체를 이용하여 풀었다.

값이 1000000 백만이 들어가서 시간초과에 안걸릴까 조마조마했는데

'맞췄습니다' 가 나왔다.

• 풀이

a, b = map(int, input().split())

max_num = 1000001
all_primelist = [True] * max_num
all_primelist[1]=False

def primelist():
    sqrt_num = int(max_num ** 0.5)

    for i in range(2, sqrt_num + 1):
        if all_primelist[i]:
            for j in range(i + i, max_num, i):
                all_primelist[j] = False
    return

def prime_num(a, b):
    for i in range(a, b + 1):
        if all_primelist[i]:
            print(i)
    return

primelist()
prime_num(a, b)

'''
# 입력
3 16
# 출력
3
5
7
11
13
'''