[Python] 소수 판별 방법, 에라토스테네스의 체

---

소수(Prime Number) : 1과 그 수 자신 이외의 자연수로는 나눌 수 없는 자연수

 

 

N이라는 수를 소수인지 판별하려면 소수의 정의에 따라 2부터 N-1까지의 수로 N을 나눠본다. 이 과정에서 어떤 수에 의해 나눠지지 않으면 N은 소수라는 것을 판별할 수 있다.

 

# 방법1

def is_primenumber(n) :
    
    if num < 2:
        return False
        
    for i in range(2, n) :	
        if x % i == 0 :	
            return False
            
    return True

 

 

다른 방법으로는 약수의 대칭적 성질을 이용하는 것이다.

16의 약수는 1, 2, 4, 8, 16 인데 4를 제외한 나머지 약수들은 서로 대칭적인 성질을 가진다.( 1x16 과 16x1 , 2x8과 8x2 )

16이 2로 나누어 떨어진다는 것은 8로도 나누어 떨어진다는 것을 의미한다.

찾고자하는 수의 중간 값을 찾아야하는데  제곱근 값으로 처리해서 구하면 된다.

 

# 방법2

import math #sqrt 사용

def is_primenumber(n) :
    
    if num < 2:
        return False
        
    for i in range(2, int( math.sqrt(n))+1 ) :
        if n % i == 0 :
            return False

    return True

 

 

 

다른 방법으로는 '에라토스테네스의 체'가 있는데 약간의 이해가 필요하다.

 

에라토스테네스의 체 : 고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법. 이 방법은 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 부른다. ( 체 : sieve )

 

 

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

 

 

하나의 수가 소수인지 판별하는것이 아닌, 특정 숫자 N 이하 소수들을 전부 구할 때 사용.

즉 범위 내 존재하는 모든 소수를 찾을 때 사용.

 

import math

def is_prime_list(n):
    sieve = [True] * (n+1) #전부 소수라고 초기 설정
    
    m = int(math.sqrt(n))
    
    for i in range(2, m+1):
        if sieve[i] == True:
            for j in range(i+i, n+1, i): #i이후 i의 배수들을 False 판정
                sieve[j] = False
                
    # 소수 목록 산출
    return [i for i in range(2, n+1) if sieve[i] == True ]

---

 

그런데 왜 제곱근까지만 판별하면 될까 ?

 

합성수는 소수 두 개의 곱으로 만들 수 있다.

예를들어 N = 6일 때(N>1) 6은 합성수에 해당한다.

​합성수의 구성인 두 소수 중 작은 수를 S, 큰 수를 L로 둔다. ( 2 : S , 3 : L )

 

 

1 < ( SL = N )

 

​S² 보다 SL이 클 것이다. ( 2² <= 2x3 )

1 < S² <= SL = N

 

​S로 N을 표현하면 다음과 같게 된다.

1 < S <= N^1/2

 

즉 N이 합성수라면(소수가 아니라면) 위의 식이 성립되는 것인데

S가 N^1/2 보다 작거나 같을 것이니 N의 제곱근까지의 범위 안에 포함될 것이다.

 

그러므로 N의 제곱근까지 판별을 하다보면 S를 거칠 것이고 합성수라면 나누어질 것이다.

어떤 수로도 나누어지지 않는다면 소수인 것이다.