에라토스테네스의 체- prime counting function

에라토스테네스의 체는 소수를 찾는 방법으로, 

2를 제외한 2의 배수를 모두 지우고, 남은 수들 중

3을 제외한 3의 배수를 모두 지우고, 또 남은 수들 중

5를 제외한 5의 배수를 모두 지우고, ... 계속 해서 남은 수들을 지워나가는 방법으로 진행하여

소수를 찾는다. 

 

이를 파이썬으로 구현하기 위해서

array 라는 배열을 하나 만들고, 우선 모두 True라고 한다.

그 후, 위에서 말한 방식대로

2를 제외한 2의 배수들을 모두 False처리 하고

3을 제외한 3의 배수들을 모두 False처리 하고

루트 N까지 위의 방법으로 지워낸다.

def prime(N):
    array = [True for i in range(N+1)]
    for i in range(2, int(N**0.5)+1):
        if array[i] == True:
            j = 2
            while i*j <= N:
                array[i*j] = False
                j+=1
 
    prime = [0]
    for i in range(2, N):
        if(array[i] == True):
            prime.append(i)
 
    return prime
 

위처럼 체를 완성시켜 소수만 남으면, 남은 소수들을 prime 이라는 리스트에 저장하는데,

이 과정은 array[i]의 값이 True인 것만 append 하면 된다.

이때 prime[0]의 값은 0인데, 이는 prime 리스트는

prime counting function으로 사용하기 위해서이다.

 

결론적으로 prime counting function (파이 함수) 와 x/ln(x) 사이에 관계가 있음을 보이기 위해

matplotlib를 이용하여 그래프를 그리면 다음과 같다.

import math
import matplotlib.pyplot as pyplot
 
def prime(N):
    array = [True for i in range(N+1)]
    for i in range(2, int(math.sqrt(N))+1):
        if array[i] == True:
            j = 2
            while i*j <= N:
                array[i*j] = False
                j+=1
 
    prime = [0]
    for i in range(2, N):
        if(array[i] == True):
            prime.append(i)
 
    return prime
 
prime = prime(100000)
 
y=[]
i=1
for x in prime[1:]:
    y.append(i*math.log(x)/x)
    i+=1
x=prime[1:]
 
pyplot.plot(x, y)
pyplot.show()
 

 

 

다음과 같이 1에 가까워짐을 알 수 있고,

실제로 확대하여 보면 1.07쯤에 가까워짐을 알 수 있다.