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보다 큰 자연수이기 때문에 반복문을 돌며 나누어 떨어지는지를 검사했다. 학교 수업 때도 동일하게 배웠는데, 저렇게 푸니까 시간초과가 떴다.
찾아보니 에라토스테네스의 체라는 개념이 나왔고 이를 이용하여 쉽게 풀 수 있었다.
