소수 구하기

bookmark

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

나의 풀이

import math

n, m = map(int, input().split())
prime_cnt = 0
for i in range(n, m + 1):
    for j in range(2, i + 1):
        if i % j == 0:
            prime_cnt += 1
    if prime_cnt == 1:
        print(i)
    prime_cnt = 0

시간 초과

모범 답안

에라토스 테네스의 체

import math

n, m = map(int, input().split())

array = [True for i in range(m + 1)]
array[1] = False

for i in range(2, int(math.sqrt(m)) + 1):
    if array[i] == True:
        j = 2
        while i * j <= m:
            array[i * j] = False
            j += 1

for i in range(n, m + 1):
    if array[i]:
        print(i)

1은 소수가 아니니깐 false 해주고

array 입력 개수만큼 만들어준다.

시간을 줄이기 위해서 math.sqrt () 제곱근을 사용해준다.

예를들어 100의 제곱근이 10 일때 10 초과는 100을 나눌수 없기 때문에

while 반복문을 돌리면서 곱한값을 false 해준다.