소수 판별 이론 (에라토스테네스의 체, 골드바흐의 추측)

소수

자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다. (1과 본인 외의 약수가 없는 수)

가장 작은 소수는 2로, 유일한 짝수이다.

 

에라토스테네스의 체 (자연수 n까지의 소수 구하는 방법)

1. n+1개 크기의 배열 생성 후 True로 초기화

2. 최소 소수인 2부터 sqrt(n)까지 확인하면서

2-1. 소수인 경우(True), 본인보다 큰 (본인을 제외) 본인의 배수를 모두 False로 바꿔줌

3. 배열에서 소수인 애들의 인덱스를 0과 1을 제외하고 리턴

 

 

sqrt(n)까지만 확인하는 이유

n까지 해도 값의 차이는 없다. 

다만, n을 소수에서 제외시킬 수 있는 약수는 sqrt(n)이하일 수 밖에 없기때문에 불필요한 연산을 없애 시간을 줄여준다.

예) n = 10 / n의 약수: 1, 2, 5, 10 / n이 2에 의해 제외됐으면 어차피 5, 10은 의미가 없다. 

-> 10이 2로 나눠지면 5로도 나눠짐 = 2의 짝인 5는 2가 있는한 의미가 없다. 

 

파이썬 코드

def primelist(n):
    arr = [True for _ in range(n+1)]

    for i in range(2, (int(len(arr)**0.5)+1)):
        if arr[i]:
            for k in range(i+i, len(arr), i):
                arr[k] = False

    return [i for i in range(m, len(arr)) if arr[i] and i != 1]

 

 

골드바흐의 추측

모든 4 이상의 짝수인 정수는 두 소수(홀수)의 합으로 나타낼 수 있다. 

 

 

소수인지 아닌지 직접 나눠보는 방식으로 판단할때

앞에서부터 모든 수로 다 나눠보지 말고 소수로만 나눠봐도 된다.

예) 어차피 4(소수의 배수)로 나눠질 애는 앞에서 2(소수)로 나눠졌음

 

 

참고

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전