[AL]에라토스테네스의 채

소수를 판별하는 문제

우리가 소수를 판별하는 문제에 있어서 다양한 해결법을 도출 할 수 있다.

대량의 소수를 판별하여야 할 때 에라토스 테네스의 채를 사용한다.

결론부터 말하자면

N까지의 소수를 구하여라

라는 문제에서 이 방법을 사용하면 좋을 것 같다.

1. N의 제곱근을 구한다.

2. 제곱근까지의 소수 여부를 판단한다.

위 알고리즘이 전부이다.

이게 가능한 이유는 다음과 같다.

어떤 수의 약수라는 것은, X = Y * Z 라는 꼴의 형태로 표현 가능하다. 이 때 최대 Y가 되는 값은 X의 제곱근 될 때이기 때문이다.

import math

def solution(n):
    answer = 0
    
    for i in range(2, n+1):
        if is_prime_num(i) == True:
            answer += 1    
    
    return answer


def is_prime_num(n):
    end = int(math.sqrt(n))
    
    for i in range(2,end + 1):
        if n % i == 0:
            return False
    return True

다음과 같이 푼다면, N까지의 소수를 구하는데에 있어서 시간 복잡도가 루트 N까지 줄게 된다. 무야호~