파이썬 소수 판별 sqrt - paisseon sosu panbyeol sqrt

소수 판별 알고리즘

소수란?

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

# 기본적인 소수 판별 방법(2부터 n-1까지 돌려보기)
def is_prime_number(x):
  # 2부터 (x - 1)까지의 모든 수를 확인
  for i in range(2, x):
  	# x가 해당 수로 나누어떨어지면
    if x % i == 0:
    	return False
  return True
  
print(is_prime_number(4)) # False

시간복잡도는 O(X)이므로 X의 크기가 크면 비효율적이다.
좀 더 효율적인 방법으로는 제곱근 까지만 확인을 하는 것이다.
예를 들자면, 16의 약수는 다음과 같다.

• [1, 2, 4, 8 16]

해당 수를 살펴보면 가운데 수를 기준으로 대칭적으로 곱을 통해 16을 만들 수 있다. 이를 통해, 소수의 절반에 해당하는 제곱근까지만 살펴보면 소수 판별이 가능하다는 것을 알 수 있다.

import math

# 제곱근까지만 보고 소수를 판별하는 함수
def is_prime_number(x):
    # 2부터 x의 제곱근까지의 모든 수를 확인하며
    for i in range(2, int(math.sqrt(x))+1):
    # x가 해당 수로 나누어 떨어진다면
    if x % i == 0:
        return False
    return True

개선된 알고리즘의 시간복잡도는 O(X^(1/2))라고 할 수 있다. 하지만, 여러 수에 대한 소수 판별에는 비효율적일 수 있다.
이러한 경우에는 에라토스테네스의 체라는 알고리즘을 활용한다.

에라토스테네스의 체

이는 범위에 대한 소수 판별에 유리하다. 하는 방법은 다음과 같다.

1. 2부터 N까지의 모든 자연수를 나열한다.
2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.
3. 남은 수 중에서 i의 배수를 모두 제거한다.(i는 제거하지 않는다.)
4. 더 이상 반복할 수 없을 때까지 2번과 3번의 과정을 반복한다.

import math

# 소수 판별 함수(에라토스테네스의 체)
def is_prime_number(n):
    # 2부터 n까지의 모든 수에 대하여 소수 판별
    array = [True for i in range(n+1)] # 처음엔 모든 수가 소수(True)인 것으로 초기화(0과 1은 제외)

    # 에라토스테네스의 체
    for i in range(2, int(math.sqrt(n)) + 1): #2부터 n의 제곱근까지의 모든 수를 확인하며
        if array[i] == True: # i가 소수인 경우(남은 수인 경우)
            # i를 제외한 i의 모든 배수를 지우기
            j = 2
            while i * j <= n:
                array[i * j] = False
                j += 1

    return [ i for i in range(2, n+1) if array[i] ]

# N이 1,000,000 이내로 주어지는 경우 활용할 것 => 이론상 400만번 정도 연산이고 메모리도 충분함

print(is_prime_number(26))

에라토스테네스의 체 알고리즘의 시간 복잡도는 O(NloglogN)으로 사실상 선형 시간에 동작할 정도로 빠르다. 하지만, N크기 만큼의 메모리를 저장하고 기억해야하므로 주의해야한다.

해당 문서는 이것이 코딩 테스트다. with 파이썬 - 나동빈 저의 책을 읽고 정리한 내용입니다.

가끔 알고리즘 문제에 나오는 소수계산을 위해 정리하는 글이다.

소수란, 1과 자기 자신 이외에 약수를 가지지 않는 1보다 큰 자연수 이다.

1은 소수가 아니다

소수 판별 알고리즘은 대표적으로 두가지 방법으로 구현 할  수 있다.

일반적인 방법

우선, 반복문을 사용하는 것이다. 

이 방법은 1개의 숫자가 소수인지 아닌지 판별하는데 사용하면 좋다.
여러 숫자를 소수 판별해야하는 경우는 아래 있는 에라토스테네스의 체가 더 유용하다.

n이라는 숫자가 소수인지 확인하기 위해서는 2부터 n-1까지 나눠보면서 나머지가 0이 나오는 숫자가 한개도 없으면 n은 소수이다. 

하지만 n-1까지 나눠보지 않더고 √n 까지만 확인해봐도 된다. 

소스코드 

import sys, math

# 소수 판별 알고리즘 : 제곱근까지 구하기
def isPrime(x):
    if x == 1: # 1은 소수가 아님
        return False
    for i in range(2, int(math.sqrt(x))+1):
        if x % i == 0:
            return False
    return True

에라토스테네스의 체

다른 방법으로는 에라토스테네스의 체가 있다. 위의 방법과 비슷하지만, 소수 판별을 해야하는 숫자가 많을 때 유리하다.

왜냐하면 리스트에 2부터 n까지에 대해 소수 여부를 저장하기 때문에 한번 계산해두고, 해당 숫자가 소수인지 확인하는 것은 O(1)이 걸리기 때문이다. 

단, 2부터 n까지의 소수 여부를 저장하는 배열이 필요하므로 그만큼 공간복잡도가 들어간다.

소스코드

import sys, math
target = 1000 # 구하려는 값의 범위
#에라토스테네스의 체
prime = [True]*(target) 
prime[1] = False # 1은 소수가 아님
m = int(math.sqrt(target))
for i in range(2, m+1):
    if prime[i] == True:
        for j in range(i+i, target, i):
            prime[j] = False