BOJ/백준 - 1929번 소수 구하기

1929 - 소수 구하기

문제

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

코드

한마디

여태껏 나는 다음과 같은 방식으로 소수를 판별했다.

count = 0
for i in range(1, N):
    if N % i == 0:
        count += 1

if count == 2:
    print("Prime number")

소수란 1과 자기 자신 외의 약수를 가지지 않는 1보다 큰 자연수이기 때문에 반복문을 돌며 나누어 떨어지는지를 검사했다. 학교 수업 때도 동일하게 배웠는데, 저렇게 푸니까 시간초과가 떴다.

찾아보니 에라토스테네스의 체라는 개념이 나왔고 이를 이용하여 쉽게 풀 수 있었다.