[Python&SQL] 소수(Prime number) 구하기

안녕하세요 

이승혁 입니다.

 

이번 시간에는 소수(Prime number)를 구하는 알고리즘을 공부해보도록 하겠습니다.

 

### 소수(Prime number) ?

 

위키피디아 정의 : 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다.

 

출처 : https://ko.wikipedia.org/wiki/%EC%86%8C%EC%88%98_(%EC%88%98%EB%A1%A0)

좌측은 소수(prime), 우측은 합성수(compoisite) 입니다.

 

좌측의 2, 3, 5, 7, 11 은 1과 자기 자신외에는 약수가 없습니다.

우측의 2, 4, 6, 8 ,9 10, 12 는 약수가 2개 이상입니다.

 

### 소수 구하는 방법 ?

 

1. 약수의 개수

 

     특징 중 약수를 자신과, 1 두 개 만을 갖는다는 것을 알았습니다.

     이를 사용해서 약수의 개수를 가지고 소수를 판별할 수 있습니다.

 

     그래서 짜본 알고리즘은 약수의 개수로 접근을 해보려합니다.

 

     코드는 다음과 같습니다.

from datetime import datetime
def get_prime(num): # 소수 구하는 함수
    prime=[]        # 소수 담을 리스트 
    for i in range(2,num+1): # 2 ~ 입력받은 수까지 범위
        cnt=0                # 약수 개수를 담을 cnt 변수
        for j in range(2,i+1): # 2 ~ 부터 첫 포믄 i 까지의 범위
            if i%j==0:       # i를 2부터 자기자신까지 나누어 약수 확인
                cnt+=1       # 약수가 있다면 cnt + 1 
        if cnt==1:
            prime.append(i)  # cnt 가 1이라면 = 약수가 1개라면 소수리스트에 추가
                             # 1을 범위에서 뺐기 때문에 약수가 1개(자기자신)
    return prime

start =datetime.now()# 함수 시작 시간
print(get_prime(100000))     # 2 ~ 100000 범위의 약수 찾기
end = datetime.now()
print('걸린 시간 : ',end-start) # 현재 시간 - 함수 시작 시간

 

결과는 잘 출력이 됐습니다.

걸린 시간이 무려 6분 15초 입니다..

 

숫자의 범위가 증가할수록 확인해야 하는 숫자가 많아지기 때문입니다.

10의 경우 1 , 2, 3, 4, 5, 6, 7, 8, 9 ,10 모두 나누어보고 약수를 구합니다.

하지만 100000 ? -> 10만번 나누기를 진행해야 합니다.

 

" 간단하지만 큰 수에는 적용할 수 없을 것 같습니다. "

 

2. 에라토스테네스의 체

 

     1. 자연수의 범위의 수를 나열한다.( 2 ~ n )

     2. 2부터 2의 배수를 지운다. 이때 2는 최초의 소수입니다. (p=2)

     3. 3은 소수입니다. 3의 배수를 지웁니다.(p=3)

 

이 방법을 다음에 지울 소수, 즉 p의 제곱이 n 보다 커질 때까지, 이 방법을 계속한다 (p^2≥n).

 

출처 : 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

 

에라토스테네스의 체 방법을 사용해서 작성한 코드입니다.

from datetime import datetime
def get_prime(num):
    import numpy as np
    import math
    
    num_list=list(np.arange(0,num+1)) # 1 ~ 100 범위 리스트
    num_list[1]=0
    m=int(math.sqrt(num))+1
    
    for i in range(2,m):
        for j in range(i*2,num+1,i):
               num_list[j]=0
    return [i for i in num_list if num_list[i]!=0]

start=datetime.now()
print(get_prime(100000))
end=datetime.now()
print('걸린 시간:',end-start)

 

- 접근 과정

 

1. 0부터 범위까지 자연수 리스트를 만듭니다. 인덱스를 사용하려고 0부터 시작했습니다.

2. 소수의 제곱근을 구합니다.

3. 제곱근을 포함시키기 위해 +1

4. 2부터 제곱근까지 첫 포문으로 사용하며, 두 번째 포문으로 첫 번째 포문의 배수 간격으로 진행

5. 해당 인덱스의 원소를 0으로 치환

6. 마지막으로 comprehension을 사용해 0이 아닌 원소들을 반환합니다.

 

걸린 시간은 0.07초 입니다.

 

### 위키피디아의 소수 구하는 코드

 

출처 : 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

 

위키피디아에도 코드가 있었습니다. 

자연수 대신 TRUE 요소를 자연수의 개수만큼 리스트로 만들어 사용했네요

pop, index 과정 대신 True를 False로 바꾸어줍니다.

마지막은 conprehesion을 사용해 True인 위치의 인덱스를 반환해 주는 코드입니다.

 

위키피디아의 작업 수행 시간은 0.01초 입니다.

직접 짠 코드보다 7배가 빠른 것 입니다.

 

- 차이점

* numpy , math 모듈을 임포트 하지 않음

* 리스트를 숫자가 아닌 boolean으로 생성

* 0.5 제곱으로 제곱근 구함

* 1을 따로 처리하지 않고 for문 범위로 해결

---

저는 읽은 그대로 받아들여 첫 떠오른 접근은 " 전체에서 뺀다 " 는 접근을 했습니다.

해당 숫자를 찾고, 위치를 찾고, 빼는 과정이 숫자가 커지면 오래 걸렸습니다.

그래서 다시 접근한 방법은 최대한 리스트의 요소를 적게 건드리고자 했습니다.

위키피디아 처럼요

 

위키피디아의 소스는" 위치를 체크 , 위치 반환 " 해주는 접근 같습니다.

같은 목적에도 여러가지 접근 방법을 사용할 능력을 기르는 것이 좋을 것 같아요

 

### SQL 소수 구하기

 

개발 보다는 데이터 관리, 분석을 목적으로 하는 SQL

간단하게 진행하도록 하겠습니다.

 

오라클 SQL로 소수 구하기

 

accept range prompt '수를 입력하세요'
with num_list as ( select level as num
                    from dual
                    connect by level<=&&range)
select n1.num
from num_list n1, num_list n2
where mod(n1.num,n2.num)=0
group by n1.num
having count(n1.num)=2
order by 1;

1~지정 범위까지의 with 절 테이블 셀프 조인합니다

나머지 연산 나머지가 0인 데이터들 중

 

피제수로 묶었을 때  개수가 2개인 경우!! --> 1과 자기 자신 뿐

소수로 판단하는 쿼리입니다.

마지막으로  정렬을 해주면 끝!

 

1 ~ 10000 범위 : 약 19초

1 ~ 100000 범위 : 오래걸려서 측정 x 

 

더 나은 코드가 있다면 댓글 부탁드립니다.

 

읽어주셔서 감사합니다.