[파이썬] 소수 (Prime Number)

[소수란 ?]

소수란 1보다 큰 자연수 중에서 1과 자기자신을 제외한 자연수로는 나누어 떨어지지 않는 자연수이다.

 

즉, 6은 1, 2, 3, 6으로 나누어 떨어지므로 소수가 아니며, 7은 1과 7을 제외한 다른 수로 나누어 떨어지지 않기 때문에 소수이다.

 

[기본적인 소수 판별 예제]

def is_prime_number(x) :
  for i in range(2, x) :
    if x % i == 0 :
      return False
  return True

print(is_prime_number(4))
print(is_prime_number(7))

 

소수 판별 함수(is_prime_number) 를 통해 2부터 x-1 까지의 모든 수를 확인하며 만약 x가 해당 수로 나누어 떨어지면

 

소수가 아니기 때문에 False를 반환하고 반대로 x가 해당 수로 나누어 떨어지지 않는다면 소수이기 때문에

 

True를 반환한다.

 

[개선된 소수 판별 예제]

import math

def is_prime_number(x) :
  for i in range(2, int(math.sqrt(x)) + 1) :
    if x % i == 0 :
      return False
  return True

print(is_prime_number(4))
print(is_prime_number(7))

 

소수 판별 함수(is_prime_number) 를 통해 2부터 x의 제곱근까지의 모든 수를 확인하며 만약 x가 해당 수로 나누어 떨어지면

 

소수가 아니기 때문에 False를 반환하고 반대로 x가 해당 수로 나누어 떨어지지 않는다면 소수이기 때문에 True를 반환한다.

 

---

출처

이것이 코딩 테스트다 with 파이썬 - 나동빈 저