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

📌 문제

💯 정답

def isPrime(n):
    if n == 1:
        return False
    for j in range(2, int(n**0.5)+1):
        if n % j == 0:
            return False
    return True             # n == 2 or 3 일때 소수지만 range를 만족하지는 않음

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

for i in range(m, n+1):
    if isPrime(i):			// return 값이 True이면
        print(i)

📝 설명

• 시간 초과가 많이 난 문제였는데 이 문제의 핵심은 함수사용, 제곱근 검사 이다.
• 나누어 떨어지는지 검사시, 해당 수의 제곱근까지만 나눠보면 된다.
  약수는 대칭으로 이루어져 있기에 2X6 이나 6X2는 같기 때문이다.
• n 이 2 또는 3인 경우도 소수지만 range를 만족하지는 않는다.
  range(2, 2)가 되어 범위를 벗어나는 경우가 되므로 이 또한 return True에 해당한다.

---

⭐️ 알고가기 _ 제곱근 구하기

1️⃣   n ** 0.5

n = 5
print(int(n ** 0.5))		// 2 출력

2️⃣   math.sqrt(n)

import math

n = 5
print(int(math.sqrt(n)))	// 2 출력