(파이썬) 소수 발생기

다음은 소수를 찾기 위해 내가 겪은 시행 착오 과정이다.

1. 자연수 \(n\) 이 소수(prime number) 인지 체크하는 가장 단순한 방법은 \(n\) 이 \(1<k<n\) 인 모든 자연수 \(k\)로 나누어 떨어지지 않는 것을 보이는 것이다. 처음에 이런 방법으로 소수들을 찾고는 스스로 만족했었다.

2.  그런데 가만히 생각해보니 \(\dfrac{n}{2}\) 보다 큰 수로는 \(n\) 이 나누어 떨어지지 않을 것이므로 \(k\) 의 범위를 \(1<k<\dfrac{n}{2}\) 로 바꿨다. 초등학생인 아들 녀석이 감탄했었다.

3. 그런데 말입니다. \(1<k<\dfrac{n}{2}\) 의 모든 자연수들이 다 필요한 것이 아니었다. 이 중에서 소수들만 확인해 보면 되는 것이 아닌가?

4. 그래서 소수들의 리스트(파이썬을 사용하고 있다.)를 만들어서 \(n\) 보다 작은 리스트의 요소 \(k\)들에 대해서만 \(n\) 이 \(k\)로 나누어 떨어지는지 확인하였다.

그래서 나온 코드이다.

primenumber=[]    # 소수들이 들어갈 빈 리스를 하나 만들고, 
for i in range(2, 100):  # 2부터 99까지에서 소수들을 골라낼 거임
    if i==2:  #  만약 2라면 그냥 primenumber에 추가하고
        primenumber.append(i)
    else:
        for j in primenumber:
            if i%j==0:   # primenumber의 요소들로 i 가 나누어 떨어지는지 확인하여
                break   # 나누어 떨어지면 소수가 아니므로 그냥 루프를 빠져 나오고
        if j==primenumber[-1]:   # 끝까지  나누어 떨어지는 놈이 없었는지 확인
            primenumber.append(i)  # 그렇다면 primenumber에 i를 추가한다.
print(primenumber)

그런데 말입니다. 또 생각을 해보니 만약 \(n\) 이 \(2\)로 나누어 떨어지지 않는다면 \(1<k<\dfrac{n}{2}\) 의 범위에서 생각하면 되고, \(3\) 으로 나누어 떨어지지 않는다면 \(1<k<\dfrac{n}{3}\) 의 범위에서 생각하면 되는 것이 아닌가? 이 과정을 소수 \(2, \; 3, \; 5,\; 7, \; \cdots\) 에 대해서 계속 해 주면 체크해야할 소수의 개수를 드라마틱(?)하게 줄일 수 있는 것이다. 

그래서 다시 만들어 본 소수 발생기...

primenumber=[2]
for i in range(3, 1000000000):
    j=0
    index=i
    while primenumber[j]<=index:
        if i%primenumber[j]==0:
            break
        else:
            index=int(i/primenumber[j])+1
        if primenumber[j]>=index or primenumber[j+1]>index:
            primenumber.append(i)
            break
        else:
            j+=1

f=open("primenumber.txt", 'w')
f.write(str(primenumber))
f.close()

너무 많아서 파일을 열어서 파일에 써 버렸다.

실제로 해 봤더니 소수를 만드는 시간이 상당히 줄어드는 것을 확인할 수 있었다.