[백준] 소수 구하기

1929번: 소수 구하기

🔗 문제

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

입력

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

3 16

출력

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

3
5
7
11
13

💡풀이 방법

• 시작하는 수와 끝나는 수를 입력받는다.
• 시작하는 수부터 끝나는 수까지 반복하는데 해당하는 수가 1이라면 반복문을 끝내는게 아닌 위로 다시 올라간다.
• 에라토스테네스의 체를 이용하여 해당하는 수의 제곱근까지만 확인한다.
• 만약 나누어 떨어지면 1이 아닌 약수가 존재하는 수이기 때문에 소수가 아니다.
• 나누어 떨어지지 않는다면 소수이기 때문에 출력한다.
  
  
  
  

💻 코드

# [1929] 소수 구하기
startNumber, endNumber = map(int, input().split())

for number in range(startNumber, endNumber+1):
    if number == 1:
        continue
    for j in range(2, int(number**0.5)+1):
        if number % j == 0:
            break
    else:
        print(number)