[알고리즘] 소수 판별하기

1. 소수

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

1-1. 선형탐색 - 약수의 성질을 이용하여 범위 최소화

모든 수 N에 대하여 소수 여부를 확인하고자 할 떄는, 선형탐색(접근)보다는 경우의 수를 최대한 낮추어 알고리즘을 적용하는 것이 중요하다(선형탐색일 경우 시간복잡도가 그만큼 비례하여 증가).

• 이때 약수의 성질을 이용하는데, 모든 약수가 가운데 해당 수의 제곱근을 기준으로 곱셈에 대한 대칭이 이루어진다는 점을 이용한다.
• 즉, 제곱근 전까지 해당 수가 나누어 떨어지는 몫이 존재하는 여부를 파악한다면 범위를 최소화할 수 있는 상태에서 소수여부에 대해 판별이 가능하다.
• 시간복잡도는 O(N^1/2)이다.

#소수 판별하기
import math

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

print(isPrimeNumber(5))

1-2. 에라토스테네스의 체 - 특정 수 범위 내에서 존재하는 모든 소수 탐색

보통은 한가지 수에 대한 소수여부보다는, 여러 수에 대해 소수여부를 판단할 수 있는지에 대해 구현할 수 있는지가 더 중요하다.

• 즉 여러개의 수에 대해 반복적으로 소수여부를 판단해야 하는 경우
• 특정 범위에 속하는 모든 소수를 구해야 하는 경우

이런 상황일 경우엔 에라토스테네스의 체 알고리즘을 활용하는 것이 더 유리하다.

N보다 작거나 같은 자연수에서 존재하는 모든 소수를 찾고자 할 때, 아래 과정을 반복한다.

• 2부터 N까지 모든 수를 나열한다.
• 최초 시작 수 i를 정한다(단 i는 일전 과정에서 처리되지 않은 수).
• i의 배수를 모두 제거한다.
• 위 과정을 반복한다.

이때 유의해야 할 점은, N이하의 수 중 소수인 수를 "남아있게 하는 것"이 중요하다는 것이다. 즉, 소수가 아닌 수들은 최초 소수에 2,3,4,..를 곱해가면서 제거되며 이 "곱해지는 소수"들은 제곱근보다 큰 수를 찾을 필요없이 작은 범위 내에서 찾는다.

다만 제거하는 수는 모든 범위에서 진행, "곱해지는 소수"만 제곱근 범위 내에서 진행

import math

# 1000까지의 소수 판별
n = 1000
array = [True for i in range(n+1)]

for i in range(2, int(math.sqrt(n))+1):
    #어떤 수의 배수들을 제거할지 판단하는 기준은
    #최초의 소수를 제외하고, 그 소수의 모든 배수를 제거한다.
    if array[i] == True: 
        j = 2
        while i * j < n:
            #소수가 아닌 수들은
            #n의 제곱근 안에 속하는 약수들에 대하여
            #그 배수들이 제거되므로
            #곱하는 수 자체는(i)는 제곱근 내부의 수
            #단 제거할 때는 모든 범위에 대해서 제거
            array[i*j] = False
            j = j + 1

#모든 소수 출력
for i in range(2, n+1):
    if array[i]:
        print(i, end=' ')