BOJ 수학 : 소수찾기(1978)

문제정의
자연수 n이 주어졌을 때, n이 소수인지 아닌지 판별하시오.

풀이1

2부터 n-1까지 나누기 연산을 해야하기 때문에 시간복잡도는 O(n)입니다.

import math

# 소수 판별 함수 (2이상의 자연수에 대해)
def is_prime_number(n):
    # 2부터 n-1까지의 모든 수를 확인하며
    for i in range(2, n):
        # x가 해당 수로 나누어 떨어진다면
        if n % i == 0:
            return False # 소수가 아님
    return True # 소수임

is_prime_number(153)

약수의 성질

n의 제곱근까지만 확인하면 됩니다.

풀이2

2부터 n-1의 제곱근까지 나누기 연산을 해야하기 때문에 시간복잡도는 O(n^(1/2))입니다.

import math

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

is_prime_number(153)

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

• 다수의 자연수에 대해 소수 여부를 판별할 때 사용하는 대표적인 알고리즘 입니다.
• 에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾을 때 사용합니다.
• 에라토스테네스의 체 알고리즘의 구체적인 동작 과정은 다음과 같습니다.

1. 2부터 N까지의 모든 자연수를 나열한다.
2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.
3. 남은 수 중에서 i의 배수를 모두 제거한다 (i는 제거하지 않는다.)
4. 더 이상 반복할 수 없을 때까지 2번과 3번의 과정을 반복한다.
   ※ n의 제곱근(5)까지만 수행하고 나면 그 후의 수 7, 9, 11, ...에 대해서는 위 과정을 반복해도 갱신되는 것이 없다.

• 남은 수 중에 아직 처리하지 않은 가장 작은수 2의 배수를 모두 제거한다.

import math

n = 100 # 2부터 100까지의 모든 수에 대해 소수 판별
# 처음엔 모든 수가 소수(True)인 것으로 초기화(0과 1은 제외)
array = [True for i in range(n+1)]

# 에라토스테네스의 체 알고리즘
# 2부터 n의 제곱근까지 모든 수에 대해서
for i in range(2, int(math.sqrt(n))+1):
    if array[i] == True: # 아직 처리되지 않은 가장 작은 소수
        j = 2 # X 2부터시작해서
        while i * j <= n: # 해당 소수의 배수를
            array[i*j] = False # 지워준다
            j += 1 # 다음 배수를 계산하기 위해 j를 증가시킨다.

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