[math2/Python] 1929번: 소수 구하기 - 효과는 굉장했다!

1929번: 소수 구하기

알고리즘 분류

• 수학
• 정수론
• 소수 판정
• 에라토스테네스의 체

 

 

SOLUTION

import sys
import math

M, N = map(int, sys.stdin.readline().split())
visited = [False] * (N+1)
visited[0] = True
visited[1] = True

for i in range(2, int(math.sqrt(N))+1):  # 시간단축을 위해 num의 제곱근까지만 탐색한다
    if not visited[i]:
        for j in range(i*2, N+1, i):
            visited[j] = True # i의 배수들은 방문처리

for i in range(M, N+1):
    if visited[i] == False:
        print(i)