728x90 소수1 [algorithm] 소수(prime number)에 대한 정의와 표현 소수 (Prime Number)의 정의 소수란 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어떨어지지 않는 자연수 소수인지를 판별하는 알고리즘 기본적인 소수 판별 알고리즘(시간복잡도 O(n) # 소수 판별 함수(2이상의 자연수에 대하여) def is_prime_number(x): # 2부터 (x - 1)까지의 모든 수를 확인하며 for i in range(2, x): # x가 해당 수로 나누어떨어진다면 if x % i == 0: return False # 소수가 아님 return True # 소수임 개선된 소수 판별 알고리즘(시간복잡도 O(n의 2분의1제곱)) import math # 소수 판별 함수 def is_prime_number(x): # 2부터 x의 제곱근까지의 모든 수를 확.. 2022. 3. 2. 이전 1 다음 728x90