소수 (prime number)
1보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어 떨어지지 않는 자연수
코딩테스트에서는 소수 판별 문제가 여러 유형으로 출제되곤 함
1. 기본적인 알고리즘
2부터 입력 - 1까지의 수들을 확인하면서 입력을 그 수로 나누었을 때 나머지가 0이면 False를 return
def is_prime_number(x):
for i in range(2, x):
if x % i == 0:
return False
return True
Python
복사
모든 수를 하나씩 확인하기 때문에 시간 복잡도는
2. 기본 알고리즘의 개선
모든 약수는 가운데 약수를 기준으로 대칭을 이루기 때문에 x의 제곱근까지만 확인하면 됨
ex ) 16의 약수 : 1, 2, 4, 8, 16 → 4를 기준으로 대칭
ex) 15의 약수 : 1, 3, 5, 15 → 짝수개라서 가운데 약수는 없지만 이하 약수들과 이상 약수들이 서로를 곱하면 15가 되도록 대칭적으로 짝지어진다.
def is_prime_number(x):
for i in range(2, int(x**0.5)+1):
if x % i == 0:
return False
return True
Python
복사
시간복잡도는
3. 에라토스테네의 체 알고리즘
이 알고리즘은 N 이하의 모든 소수를 찾을 때 사용이 가능하다.
1.
2부터 N까지 모든 자연수를 나열한다.
2.
나열된 숫자 중 가장 작은 수를 x로 지정한다.
3.
나열된 숫자 중 x의 배수를 모두 제거한다. (x는 제거하지 않음)
4.
더 이상 반복할 수 없을 때까지 2와 3을 반복한다.
def find_prime_number(x):
# x이하의 모든 소수 찾기
array = [True for _ in range(x + 1)]
for i in range(2, int(x**0.5 + 1)):
j = 2
while i * j <= n:
array[i*j]
j += 1
for i in range(2, x + 1):
if array[i]:
print(i) # 소수 출력
Python
복사
그러나 이 방식은 N 크기만큼의 리스트를 할당해야해서 많은 메로리를 필요로 한다.
x가 약 10억 이상이 된다면 다른 알고리즘을 찾아보는 것이 좋다.
