소수 판별 알고리즘
June 24, 2021
소수(Prime Number)
2보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어떨어지지 않는 자연수
소수의 판별
def isPrimeNumber(x):
# 2부터 (x-1)까지의 모든 수 확인
for i in range(2, x):
if x % i == 0:
return False
return True
print(isPrimeNumber(7)) # True
print(isPrimeNumber(8)) # False시간 복잡도 : O(X), 비효율적이므로 개선 필요
바로 가운데 약수까지만 나누어떨어지는지 확인 -> 제곱근까지만 확인
import math
def isPrimeNumber(x):
for i in range(2, int(math.sqrt(x))+1):
if x % i == 0:
return False
return True시간 복잡도 : O(√X)
에라토스테네스의 체
여러 개의 수가 소수인지 아닌지 판별할 때 사용
import math
n = 100 # 2부터 n까지의 모든 수에 대하여 소수 판별
array = [True for _ in range(n+1)] # 모든 수가 소수(True)로 초기화(2부터)
for i in range(2, int(math.sqrt(n))+1): # 2부터 n의 제곱근까지 수 확인
if array[i] == True:
j = 2
# i를 제외한 i의 모든 배수를 지우기
while i*j <= n:
array[i*j] = False
j += 1
# 2부터 n까지의 수 중 소수만 출력
for i in range(2, n+1):
if array[i]:
print(i, end=' ')시간 복잡도 : O(NloglogN)
매우 빠르게 동작, 하지만 메모리가 많이 필요하다는 단점이 있음
참조
- 이것이 취업을 위한 코딩 테스트다 with 파이썬
