[Algo] 에라토스테네스의 체

소수의 갯수를 구하던 기존 방식의 수행 시간은 O(N)

• 에타로스테네스의 체 방식을 활용하면 수행시간을 O(N^(1/2))로 줄일 수 있다.

알고리즘 개념

• 어떠한 자연수 N 이하의 약수들 중 소수를 판별하는 방법.
• 소수 또는 합성수가 아닌 1을 제외한다.
• 자연수 2부터 차례대로 진행하여 현재 수의 배수를 지운다.
• 남아 있는 수는 소수가 된다.

from worktime import wk

@wk.performance_time
def prime_num(data):
    result = [True] * data

    for i in range(2, data + 1):
        if result[i - 1]:
            for j in range(i * 2, data + 1, i):
                result[j - 1] = False
    cnt = sum(map(lambda x: x == True, result))
    return cnt - 1


data = 15238

print(prime_num(data))

위 본인이 작성한 함수는 소수의 개수를 구하는 함수지만
어떤 수가 소수인지 알아내는 것은 더 쉬움!