소수 판별 알고리즘

😎 소수 판별 알고리즘

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

• 코테에서 활용해야 하는 문제가 나오기도 한다.

소수 판별 기본 알고리즘

import sys
# sys.stdin = open("input.text", "rt")

#소수 판별 함수(2 이상의 자연수에 대하여)
def is_prime_number(x):
    #2부터 x-1까지의 모든 수를 확인하며
    for i in range(2,x):
        if x % i == 0:
            return False   #소수가 아님.
    return True  #소수임

print(is_prime_number(6))
print(is_prime_number(7))

소수 판별 알고리즘의 성능 분석

2부터 n-1까지의 모든 자연수에 대하여 연산을 수행하기에 시간 복잡도 O(N)

성능 개선을 위해 약수의 성질 이용.
모든 약수가 가운데 약수를 기준으로 곱셈 연산에 대해 대칭을 이룬다.

• 예를 들어 16의 약수는 1,2,4,8,16
• 이 때, 2x8 = 16, 8x2 = 16 대칭이다.

따라서 특정한 자연수의 모든 약수를 찾을 때 가운데 약수(제곱근)까지만 확인하면 돼!!!

• 예를 들어, 16이 2로 나누어 떨어진다는 것은 8로도 나누어 떨어진다는 것을 의미.
• 그렇기에 뒤까지 확인할 필요가 없음

개선된 소수 판별 코드

import sys
import math
# sys.stdin = open("input.text", "rt")

#소수 판별 함수(2이상의 자연수에 대하여)
def is_prime_number(x):
    #2부터 x의 제곱근까지의 모든 수를 확인하며
    for i in range(2, int(math.sqrt(x)) + 1):   #제곱근에 1을 더해줌으로써 실질적으로 제곱근까지 확인!
        #x가 해당 수로 나누어 떨어진다면
        if x % i == 0:
            return False
    return True

#이렇게 제곱근까지만 확인한다면 뒤에 역시 동일하게 나온다는 걸 아니깐 시간복잡도에서 이득!
print(is_prime_number(4))
print(is_prime_number(7))

개선된 코드는 2부터 n의 제곱근까지의 모든 자연수에 대해서 연산을 수행하기 때문에

• 시간 복잡도는 O(N^(1/2)) 이다.

이제까지 하나의 수에 대해서 소수인지 아닌지를 판별하는 방법을 배웠다.

-> 특정한 수의 범위 안에 존재하는 모든 소수를 찾아보자.

에라토스테네스의 체 알고리즘

이 알고리즘은 특정 범위 안에 존재하는 각각의 자연수들이 소수인지 아닌지를 한꺼번에 계산하고자 할 때 효과적으로 사용 가능.

동작 과정

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

이 과정을 수행하면 2부터 N까지 모든 자연수에 대하여 어떤 수가 남아 있는지를 확인해서 그 남아있는 수들이 모두 소수라고 판단할 수 있다.

import math
# sys.stdin = open("input.text", "rt")

N = 1000 #2부터 1000까지의 모든 수에 대하여 소수 판별
#처음엔 모든 수가 소수인 것으로 초기화(0과 1인 제외)
array = [True] * (N+1)
array[0] = False  #0,1제외
array[1] = False  #0,1제외

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

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

알고리즘 성능 분석

에라토스테네스의 체 알고리즘의 시간 복잡도는 사실상 선형 시간에 가까울 정도로 매우 빠르다.

• 시간 복잡도는 O(NloglogN)

😎 에라토스테네스의 체 알고리즘은 다수의 소수를 찾아야 하는 문제에서 효과적으로 사용될 수 있다 !!