[백준] 1929번: 소수 구하기 / 파이썬

문제 링크

---

https://www.acmicpc.net/problem/1929

 

 

풀이 코드

---

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

for i in range(n,m+1):  #n~m 사이의 수를 모두 검사
    if i == 1:  #1이라면 그냥 넘어감
        continue
    for j in range(2,int(i**0.5)+1):  #2부터 i의 제곱근까지의 수로 나눠지는지
        if i % j == 0:  #나눠진다면 소수가 아님
            break
    else:
        print(i)  #안나눠진다면 소수

코드 해석

---

"에라토스테네스의 체" 가 핵심 포인트다.

즉 구하려는 수 x가 2부터 x의 제곱근까지의 수로 나눠지는지만 확인하면 소수인지 아닌지 판별이 가능하다.