소수 판별 알고리즘 (에라토스테네스의 체)

소수 (Prime Number) 란,

1과 자기 자신으로만 나누어지는 숫자 (단, 1은 소수가 아님)

 

(1) 특정 N 이 주어졌을 때, 이 숫자가 소수인지 아닌지 판별하기

: N이 n * m (n<=m) 으로 만들어진다고 했을 때, n <= N^1/2 (제곱근) 이다.

즉, 2~N의 제곱근 까지의 모든 수에서 N이 나누어 떨어지지 않을 때 N은 소수라고 정의할 수 있다.

-> N의 제곱근 만큼 반복하기 때문에 시간복잡도는 O(N^(1/2)) 이다.

 

[Python 코드]

import math
def solution(N):
    
    answer = True
    for n in range(2, int(math.sqrt(N)) + 1):
        if N % n == 0:
            answer = False
            break
    
    return answer

 

 

(2) N까지의 범위가 주어졌을 때, 소수를 찾아내기 (에라토스테네스의 체)

: 2~N까지 숫자 중에서 제일 작은 숫자 n을 소수로 지정하고, n의 배수가 되는 모든 수를 소수 후보에서 제외한다.

제외되지 않은 숫자 중 가장 작은 다음 숫자 m을 소수로 지정하고, m의 모든 배수를 소수 후보에서 제외한다...

모든 숫자가 지정될 때 까지, 위 작업을 반복하며 소수를 찾아낸다.

출처: https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

[Python 코드]

def solution(N):
    
    li = [True for _ in range(2, N+1)]
    
    for idx, val in enumerate(li):
        i = idx+2
        if val == False :
            continue
        for j in range(2,N):
            if i*j > N:
                break
            li[i*j-2] = False
            
    answer = filter(lambda x: x == True, li)
    
    return len(list(answer))

 

---

[참고] velog.io/@koyo/python-is-prime-number

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