#1929 소수 구하기🫥

문제📝

결과😍

코드💻

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

for i in range(m,n+1):
  if i == 1:
    continue
  for j in range(2,int(i**0.5)+1):
    if i%j == 0:
      break
  else:
    print(i)

풀이💡

에라토스테네스의 체(소수 구하기) 문제이다.

1. 1은 소수가 아니므로 제외해준다(처음에 이 부분을 간과해서 오류가 났다)
2. 반복문의 범위는 2부터 int(i**0.5)+1
   특정 수의 제곱근을 구해서 그 제곱근까지의 약수를 구하면 해당 약수를 포함하는 수를 모두 제거할 수 있다.(소수가 아니기 때문에) 이렇기 때문에 범위를 위와같이 설정(그렇지 않으면 시간초과가 발생!)

• i=12에서 12의 약수는 1 2 3 4 6 12
  int(sqrt(12))=3이고 12는 3으로 나누어 떨어지므로 더 검사할 필요가 없다.

3. i가 j로 나누어떨어지면 소수가 아니기에 break
4. 결과적으로 나누어떨어지는 수가 없으면 print

---

참고🙏

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