파이썬 소수 판별 알고리즘

minan·2021년 6월 22일
0

이것이 취업을 위한 코딩 테스트다 with 파이썬
이것이 취업을 위한 코딩 테스트다 with 파이썬의 내용

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

ex) 7은 1과 7만으로 나누어떨어지므로 소수

어떤 수 x가 소수인지 아닌지 판별하는 방법

  • 가장 간단한 방법은 x를 2부터 x-1까지의 모든 수로 나누어보는 것 만약 2부터 x-1까지 나누었을 때 나누어떨어지는 수가 하나라도 있다면 x는 소수가 아니다.

간단한 소수 판별 알고리즘 O(N)

def is_prime_number(x):
  for i in range(2, x):
  	if x % i == 0:
           return False
  return True
profile
https://github.com/minhaaan

0개의 댓글