[algorithm][python] 에라토스테네스의 체와 소수

소수에 대한 알고리즘은 제대로 알아두는게 좋을 것 같다.

[내가 보려고 적는 파이썬] 소수 판별(에라토스테네스의 체)

이 글을 참고함

import math
n=int(input())
nums=list(map(int,input().split()))
sum=0

def is_prime_number(x):
    if(x<2): return False
    for i in range(2, int(math.sqrt(x)+1)):
        if (x%i) == 0:
            return False
    return True

for i in range(n):
    if(is_prime_number(nums[i])==True):
        sum+=1
print(sum)

기본적으로 for문을 통해 하나하나 나머지를 따져보면 n의 시간복잡도가 나온다.

하지만 소수 판별에서 제곱근의 수까지만 확인해도 결과가 같다는 점을 활용하면 복잡도를 n^(1/2)로 줄일 수 있다.

에라토스테네스의 체

: 2부터 n까지의 소수 판별에 유리하다. O(NloglogN)의 시간복잡도를 얻을 수 있어 사실상 선형 시간에 동작할 정도.

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))