안녕하세요~ 마무입니다. 이번 포스트에서는 "파이썬 소수 구하기", "소수 알고리즘"에 대해서 쉽고 자세히 설명해보려고 합니다.
저는 파이썬 언어를 주로 사용하기에, 파이썬을 이용해 구현할 것이며 이해를 돕기 위해 가장 기본적인 소수 구하기 알고리즘부터 차례대로 최적화 방법을 적용한 알고리즘까지 보여드릴겁니다!
-----목차-----
1. 소수란
2. 기본 소수 알고리즘
3. 짝수 배제 소수 알고리즘
4. 모든 자연수는 소수의 곱을 이용한 알고리즘
5. 제곱근을 이용한 소수 알고리즘
6. 정리
---------------
더 많은 정보는
프로그래밍 페이지 : https://mamu2830.blogspot.com/p/blog-page_33.html
에 있을 수 있습니다!
1. 소수란
다들 알고 계신 개념이겠지만, 확인차 다시 한번 '소수'라는 개념을 설명하자면 '소수'란 '1'과 '자기자신'으로만 나누어 떨어지는 수(나누었을 때 나머지가 0)를 의미합니다.
예를 들어 '4'는 나누었을 때 나머지가 0인(나누어 떨어지는) 약수가 "1, 2, 4", 총 3개니소수가 아니죠.
여기서 개인적으로 저는 '소수'의 조건을"약수가 2개뿐인 수"라고 외우고 있습니다. 왜냐면 모든 양의 정수(자연수)는 반드시 '1'과 '자기자신', 즉 2개 이상의 약수를 갖고 있기 때문에, 약수가 2개뿐이라는 건 소수라는 것과 같은 말이니까요!
2. 기본 소수 알고리즘
가장 기본적인 소수를 구하는 알고리즘은 반복문과 조건문, 그리고 소수의 가장 기본적인 조건 '소수는 약수가 2개 뿐'을 알면 구현할 수 있습니다.
사람들마다 만드는 알고리즘은 상이하겠지만, 저는 가장 기본적인 소수 알고리즘을 이렇게 만들어보았습니다.
참고로 공부하시는 분들의 이해를 돕기 위해 주석을 아주 많이 달았으니, 코드의 설명은 주석 부분을 봐주시면 감사하겠습니다.
# '''10, for 문과 "소수는 약수가 2개"라는 조건을 이용해 구하는 함수
def count_prime1(number: int) -> list:
op_cnt = 0 # operation_count : 실행 횟수
primes = [] # primes : 소수들
# 1은 소수가 아니니 2부터 계산하며, 정확히 number 숫자까지 계산하기 위해 number + 1을 함
# ex) range(2, 100) --> 2부터 99까지 총 100번, range(2, 101) --> 2부터 100까지 총 101번
for n in range(2, number + 1):
# 어짜피 자연수는 모두 1과 자기자신으로 나누어 떨어지니, 2부터 시작해 n보다 작은 수로
# 모두 나눴을 때 한번도 나누어 떨이지지 않으면 약수가 2개라는 것이니, 소수
# ex) range(2, n) --> 2, 3, 4, ..., n-1
for i in range(2, n):
# 계산할 때마다 계산횟수인 op_cnt를 증가
op_cnt += 1
# 만약 n을 i로 나눴을 때 나머지로 0이 나온다는 것은, 1과 자기자신 외 약수가 하나 더
# 있다는 것이니 소수가 아니므로 for문 탈출
if n % i == 0:
break
# 만약 2부터 n-1까지 for문을 모두 실행했을 때 break가 발생하지 않을 시 else 문을 실행
else:
# 소수 추가
primes.append(n)
print(f"나눗셈을 한 횟수 : {op_cnt}")
print(f"2~ {number} 이하에서의 소수의 갯수 : {len(primes)}")
# 소수가 들어있는 리스트 반환
return primes
# '''
당연히 성능이 얼마나 개선되는지 알기 위해, 지금 만든 가장 기본적인 알고리즘의 성능을 측정해봐야죠?
import time
# 총 실행 시간을 저장할 변수
time_sum = 0
# 반복할 횟수를 저장할 변수
op_cnt = 1000 # operation_count : 실행 횟수
for idx in range(op_cnt):
# 코드 실행 전, 현재 시각을 time1에 저장
time1 = time.time()
# 실행시간 테스트할 알고리즘
count_prime1(10000)
# 알고리즘 실행 이후 현재 시각(time.time())에서 아까 저장해놓은 실행전 시간 time1을 빼서
# 알고리즘 실행 시간을 구해서 op_time 에 저장
op_time = time.time() - time1
# 총 실행시간을 구하기 위한 time_sum
time_sum += op_time
print(f"실행시간은 {op_time}입니다. ")
print(f"코드 반복 횟수는 {op_cnt}이며, 평균 실행시간은 '{time_sum / op_cnt}'초 입니다.")
위에서 만든 가장 기본적인 소수 알고리즘 count_prime1에 10000을 넣고, time.time()함수를 이용해 1000번 반복해보고, 평균 실행시간을 측정해보겠습니다.
제 노트북에서 가장 단순한 소수 알고리즘 함수, 'count_prime1'의 평균 실행 시간은 0.54467...초라고 하네요.
그리고 나눗셈을 한 횟수는 5775223입니다.
3. 짝수 배제 소수 알고리즘
가장 기본적인 소수를 구하는 알고리즘은 제 노트북에서10000이하의 소수를 구할 때, 평균 약 0.5447초가 걸렸습니다.
컴퓨터의 성능은 속도이며, 동일한 하드웨어에선 바로 알고리즘(소프트웨어)의 계산 속도가 컴퓨터 성능 차이를 만들어내죠!
그래서 우린 여기서 만족하지 않고, 소수를 구하는 알고리즘의 계산 속도를 향상시키기 위해 조건을 더 추가할 것입니다.
여기서 추가하는 조건이란 바로! 2를 제외한 소수는 '홀수'라는 것과 '홀수의 약수는 홀수로만 이루어져있다'는 것입니다.
왜냐면 특정 수의 약수에 짝수가 들어있다면, 그 수는 반드시 짝수가 되니까요.
이해를 돕기위해 한번 가장 기본적인 짝수 '2'를 곱해서홀수가 나오는 정수가 있는지 생각해보시면 없다는 걸 알게 될겁니다. ex) 175 x 2 = 짝수, 133 * 2 = 짝수, 8573 * 2 = 짝수
이말은 짝수랑 곱하면 반드시 짝수가 나온다는 것이고, 반대로 홀수의 약수엔 짝수가 없음을 의미하죠.
즉! 짝수와 홀수 모두 계산하던 기본 소수 알고리즘에, '2를 제외한 소수는 홀수'와 '홀수의 약수는 홀수로만 이루어져있다' 조건을 추가해 홀수만 계산하면 계산속도를 증가시킬 수 있는 것이죠!
제가 위 조건을 적용한 알고리즘 코드는 바로 이겁니다.
# 소수는 2빼고 모두 홀수라는 것과 홀수의 약수는 홀수뿐이라는 것을 이용한 소수 알고리즘
def count_prime2(number: int) -> list:
op_cnt = 0 # operation_count : 실행 횟수
# 소수는 2를 제외하곤 모두 홀수니, 귀찮은 2는 소수 리스트에 넣고 시작
primes = [2] # primes : 소수들
# 최소 소수 홀수인 3부터 2씩 증가해 홀수들만, number + 1까지 반복하겠다
# ex) range(3, 10, 2) --> 3 5 7 9
for n in range(3, number + 1, 2):
# 홀수인 n에는 짝수가 들어있지 않으니, 홀수 i로만 나눈다.
# 소수의 조건은 약수가 2개며, 모든 자연수는 기본적으로 약수를 2개를 가지고 있기에
# 한번이라도 n이 홀수로 나누어 떨어지면 약수가 3개 이상이 되니, 소수가 아님
# ex) range(3, 5, 2) --> 3 , range(3, 7, 2) --> 3, 5, range(3, 9, 2) --> 3, 5, 7
for i in range(3, n, 2):
# 계산 카운트로 op_cnt 1증가
op_cnt += 1
# 만약 n을 i로 나눠서 0이 나온다 --> 약수가 3개 이상이라는 것이니 n + 1로 넘어간다
if n % i == 0:
break
# 위 for 문이 끝날 때까지 break가 발생하지 않을시, 2개뿐이라는 거니 else문 실행
else:
primes.append(n)
print(f"나눗셈을 실행한 횟수 : {op_cnt}")
print(f"찾은 소수의 개수 : {len(primes)}")
return primes
똑같이 좀 더 향상시킨 count_prime2 알고리즘의 평균 실행 시간을 알아보겠습니다.
import time
# 총 실행 시간을 저장할 변수
time_sum = 0
# 반복할 횟수를 저장할 변수
op_cnt = 1000 # operation_count : 실행 횟수
for idx in range(op_cnt):
# 코드 실행 전, 현재 시각을 time1 에 저장
time1 = time.time()
# 실행시간 테스트할 알고리즘
count_prime2(10000)
# 알고리즘 실행 이후 현재 시각(time.time())에서 아까 저장해놓은 실행전 시간 time1을 빼서
# 알고리즘 실행 시간을 구해서 op_time 에 저장
op_time = time.time() - time1
# 총 실행시간을 구하기 위한 time_sum
time_sum += op_time
print(f"실행시간은 {op_time}입니다. ")
print(f"코드 반복 횟수는 {op_cnt}이며, 평균 실행시간은 '{time_sum / op_cnt}'초 입니다.")
이렇게 같은 노트북의 같은 조건에서 실행을 시킨 결과는
count_prime2인 경우 평균 실행 시간이 0.29377...로 약 0.2938초가 걸렸네요!
count_prime1인 경우 0.5447초였었으니 약 1.85배정도 빨라졌네요!
나눗셈을 한 횟수는 2884498로, 5775223보다 약 2배 이상 계산횟수가 줄어들었네요!
4. n 이하의 소수로 나누어 판단하는 알고리즘
자 '산술의 기본정리'라는 수학적 정리가 있습니다.
간단히 말하자면, 2 이상의 모든 자연수는 유일한 소인수분해로 표현할 수 있다인데요.
더 와닿게 표현하자면 2 이상의 모든 자연수는 소수들만의 곱으로 표현할 수 있다는 것입니다.
ex) 2 = '2', 6 = '2 x 3', 8 = '2 x 2 x2', 38 = '2 x 19', 125 = '5 x 5 x 5'
이렇게 자연수들이소수들로만 이루어진 것을 말이죠.
우리는 이제 이 정의를 이용해 소수인지 아닌지를 판단하기 위해 나누는 횟수를 줄일 수 있습니다.
바로! 자연수 n을 자연수 n보다 작은 홀수들로 나누었을 때 나누어 떨어지는 경우가 있는지를, n보다 작은 소수들로 나눌 때, 나누어 떨어지는 경우가 있는지로 바꿔서 말이죠!!
왜냐? 산술의 기본정리에 의해 2 이상의 모든 자연수는 소수들의 곱으로 표현할 수 있고, 이 말은 반대로, 2 이상 자연수는 소수들의 곱으로 이루어져있으니, 나눌 때 소수로만 나누면 된다는 것이죠!
위 그림처럼 결국 나눌 때 홀수보다 더 적은 범위(2제외)인 소수로 나누니, 계산하는 범위가 줄어드어 계산 속도가 빨라지는 것이죠!
자 그럼 지금까지의 소수 알고리즘 조건
1. 소수는 약수가 2개
2. 2이상의 소수는 홀수
에
3. 2이상의 자연수는 소수들의 곱으로 이루어져 있다
를 더해서 알고리즘 속도를 더욱 향상시켜보겠습니다.
# 소수는 2빼고 모두 홀수 + 홀수의 약수는 홀수뿐 +
# 2이상의 자연수는 소수의 곱을 이용한 소수 알고리즘
def count_prime3(number: int) -> list:
op_cnt = 0 # operation_count : 실행 횟수
# 소수는 2를 제외하곤 모두 홀수니, 귀찮은 2는 소수 리스트에 넣고 시작
primes = [2] # primes : 소수들
# 최소 소수 홀수인 3부터 2씩 증가해 홀수들만, number + 1까지 반복하겠다
# ex) range(3, 10, 2) --> 3 5 7 9
for n in range(3, number + 1, 2):
# 지금까지 저장된 소수의 개수, len(primes)만큼 반복한다
for i in range(len(primes)):
# 계산 카운트로 op_cnt 1증가
op_cnt += 1
# 만약 n을 지금까지 찾은 소수들로 나누다가한번이라도 나누어 떨어지면, 약수가 3개
# 이상이라 소수가 아니니 break 하고 다음 숫자 n + 1를 실행
if n % primes[i] == 0:
break
# 위 for 문이 끝날 때까지 break가 없을 시, 현재 n의 약수가 2개뿐이라는 거니 else문 실행
# 하여 소수리스트에 n을 추가
else:
primes.append(n)
print(f"나눗셈을 실행한 횟수 : {op_cnt}")
print(f"찾은 소수의 개수 : {len(primes)}")
return primes
위 count_prime3를 똑같이
import time
# 총 실행 시간을 저장할 변수
time_sum = 0
# 반복할 횟수를 저장할 변수
op_cnt = 1000 # operation_count : 실행 횟수
for idx in range(op_cnt):
# 코드 실행 전, 현재 시각을 time1에 저장
time1 = time.time()
# 실행시간 테스트할 알고리즘
count_prime3(10000)
# 알고리즘 실행 이후 현재 시각(time.time())에서 아까 저장해놓은 실행전 시간 time1을 빼서
# 알고리즘 실행 시간을 구해서 op_time 에 저장
op_time = time.time() - time1
# 총 실행시간을 구하기 위한 time_sum
time_sum += op_time
print(f"실행시간은 {op_time}입니다. ")
print(f"코드 반복 횟수는 {op_cnt}이며, 평균 실행시간은 '{time_sum / op_cnt}'초 입니다.")
10000이하의 번호로 1000번 반복해, 평균 실행시간을 구해보면
산술의 기본정리를 적용해 만든 count_prime3의 평균 실행시간은 약 0.0928초로, 약 0.2938초이던 count_prime2보다 대략 3.16배나 빨라졌네요!
나눗셈 횟수도 771632로, count_prime2의 2884498보다 약 3.73배나 줄어들었네요!
5. 제곱근을 이용한 소수 알고리즘
자.. 여기서 끝이 아니라 산술의 기본정리를 적용한 count_prime3을 보다 더 빠르게 만드는 방법이 있습니다.
바로 소수인지 판별하기 위해 나눌 때, 대칭되는 계산식을 제외하는 것인데요, 무슨 말이냐면
원래 특정 수를 이루는 약수는 항상 순서만 바꾼 똑같은 값의 대칭식이 있습니다.
예를 들자면
50의 약수는 1, 2, 5, 10, √(50), 25, 50으로, 그 50을 만들 수 있는 조합은
"1*50, 2*25, 5*10, √(50)*√(50), 10*5, 25*2, 1*50" 이렇게라 볼 수 있는데요.
사실상 √(50) 이후에는 순서만 바꾼 √(50)앞과 같은 계산식(대칭식)인 걸 볼 수 있죠? 그래서 여기서 깨달음을 얻은 것입니다.
아! 사실상 √(50)이하의 약수들만 계산을 하면 되겠구나! 라고요.
그래서 위 깨달음을 통해 원래 맨 처음의 소수 판별식인
n을 n 이하의 수로 모두 나눠서, 나눠떨어지는 수가 3개 이상이면 소수가 아니다를
n을 √(n)이하의 수로 모두 나눠서, 나눠떨어지는 수가 3개 이상이면 소수가 아니다!로
줄일 수 있는 겁니다.
그런데 여기서 우리는 이미 지금까지 계산 속도를 높이기 위해 소수 판별식을'n 이하의 수들로 나누기' -> 'n 이하 홀수들로 나누기' -> 'n 이하 소수들로 나누기'까지 범위를 줄였왔었죠?
그러므로 지금까지의 'n을 n이하 소수들로 나누기'에 n을 √(n)이하의 수들로 나눠서, 나눠떨어지는 수가 3개 이상이면 소수가 아니다! 이론을 합쳐서! 결국!
우린 n을 √(n)이하의 소수들로 나눠서, 나눠떨어지는 수가 3개 이상이면 소수가 아니다!로 업그레이드 시킨다는 겁니다.
그림으로 표현하자면 우린 결국
이렇게까지 소수인지 판별하기 위해 나누는 횟수 범위를 줄일 수 있는 것이죠!
결국 이렇게 만든 n을 √(n)이하의 소수로 모두 나눠서, 나눠떨어지는 수가 3개 이상이면 소수가 아니다!
를 적용해 만든 최종 소수 알고리즘(저의)은
def count_prime4(number: int) -> list:
op_cnt = 0 # operation count : 실행 횟수
# 소수 2를 제외한 모든 소수는 홀수니, 귀찮은 2는 리스트에 넣어놓고 시작
primes = [2] # 소수들을 담을 리스트
# 소수 2는 이미 들어있으니 3부터 시작해, 홀수만 계산함
# ex) range(3, 5, 2) -> 3, range(3, 6, 2) -> 3, 5이므로
# number + 1을 해준 것
for n in range(3, number + 1, 2):
# 인덱스용 변수로, 소수 2부터 시작 하며, for문 실행때마다 0으로 초기화i = 0# √n 보다 작은 범위의 소수로 나누는 것이란 "primes[i]<= sqrt(n)"보다는
# 루트를 제거하기 위해 양변을 제곱한 "primes[i] * primes[i] <= n"이 더 파이썬에서
# 계산이 더 빠르므로 "primes[i] * primes[i] <= n"를 이용함
while primes[i] * primes[i] <= n:
# primes[i] * primes[i]에서 1번, 밑에 n % primes[i]에서 1번 총 2번 계산하므로
# 2번씩 카운트 계산
op_cnt += 2
# 만약 현재 홀수 n을 루트 n보다 작은 소수로 나눴을 때 나눠떨어진다면
# 1과 자기자신 외 약수가 1개 더 생기니, 소수가 아니므로 다음 n으로 넘어감
if n % primes[i] == 0:
break
i += 1
# 루트 n보다 작은 소수들로 모두 나눴을 때 한번도 나눠떨어지지 않으면
# 약수가 1과 자기자신뿐인 소수라는 거이니, while 문이 끝나면 else 문을 실행해
# 소수 리스트에서 현재 n을 추가
else:
primes.append(n)
print(f"곱셈과 나눗셈을 실행한 횟수ex : {op_cnt}")
print(f"찾은 소수의 개수 : {len(primes)}")
return primes
이렇게 됩니다.
여기서 √(n) 대신 n을 쓰기 위해, prime[i] * primes[i]로 변경한 것은 주석에 써 놓았지만
왜 primes[i] ** 2 이렇게 쓰지 않느냐 궁금하실 분이 있을까바 말해드리자면!
제가 시도해본 결과 신기하게도 "primes[i] ** 2"보다 primes[i] * primes[i]가 더 계산 속도가 빨랐습니다.
import time
# 총 실행 시간을 저장할 변수
time_sum = 0
# 반복할 횟수를 저장할 변수
op_cnt = 1000 # operation_count : 실행 횟수
for idx in range(op_cnt):
# 코드 실행 전, 현재 시각을 time1에 저장
time1 = time.time()
# 실행시간 테스트할 알고리즘
count_prime4(10000)
# 알고리즘 실행 이후 현재 시각(time.time())에서 아까 저장해놓은 실행전 시간 time1을 빼서
# 알고리즘 실행 시간을 구해서 op_time 에 저장
op_time = time.time() - time1
# 총 실행시간을 구하기 위한 time_sum
time_sum += op_time
print(f"실행시간은 {op_time} 입니다. ")
print(f"코드 반복 횟수는 {op_cnt}이며, 평균 실행시간은 '{time_sum / op_cnt}'초 입니다.")
늘 그랬듯 성능확인을 위해 10000번 이하로 1000번 반복해보면
count_prime4의 평균 실행 시간은 0.008162...로 약 0.0081초, 계산 횟수는 77508로
약 0.0928초이며 계산 횟수는 771632 인 count_prime3보다실행시간은약 11.4배 빨라졌고, 계산횟수는약 10배 줄어들었네요!
자~~ 결국 지금까지 말한 모든 방법들을 동원해서 10000이하의 소수를 구할 때, 0.5447초가 걸리고 계산 횟수는 5775223나 나온 기본 소수 알고리즘 'count_prime1'보다 최종 'count prime4'는 0.0081초, 계산횟수 77508로 실행 시간은 약 67배 빨라졌고, 계산 횟수는 약 74.5배 줄어들었네요
여기까지가 현재 제가 아는 가장 빠른 파이썬에서 소수 구하는 알고리즘 방법이였습니다.
6. 정리
a) '소수'의 조건은 "약수가 2개뿐인 수" == 약수가 3개 이상이면 소수가 아니다
b) 2를 제외한 소수는 '홀수'
c) 2 이상 자연수는 소수들의 곱으로 이루어져있으니, 나눌 때 소수로만 나누면 된다
d) 최종 소수 알고리즘 조건 : n을 √(n)이하의 소수들로 나눠서, 약수가 3개 이상이면 소수가 아니다
e) "√(n) >= 소수" 형태 코드보다 양변을 제곱한 "n >= 소수 * 소수" 코드가 더 계산이 빠르다
이야 이번에 개인적인 공부 + 정리겸 소수 알고리즘에 대해서 포스트 해봤는데요... 정말 가볍게 시작한 것 치고 스스로 계속 코드 연구를 하다보니 생각보다 오래 걸려 3일이나 걸렸네요 ㅠㅠ
생각보다 정말 많은 노력을 기울인 만큼 제 글을 읽는 분들에게 꼭 도움이 되길 바라며!
더 좋은 알고리즘이나 잘못된 부분이 있다면, 친절히 알려주시면 정말 감사하겠습니다!
도움이 되셨다면따뜻한 댓글 및 팔로우 클릭은 저에게 큰 힘이 돼 포스트 퀄리티를 향상시킵니다!
그럼 다음에 더 좋은 포스트로 찾아뵙겠습니다!
댓글 없음:
댓글 쓰기
#1 여러분들이 소중한 시간을 투자해 달아주시는 따뜻한 댓글들은 저에게 정말 큰 힘이 됩니다!
#2 저의 각 포스트들은 엄청난 노력과 시간 투자를 통해 만들어진 포스트들로, 무단 복제나 모방하는 것을 금지합니다.
#3 저의 포스트에도 틀린 정보가 있을 수도 있습니다. 그럴 경우 친절한 말투로 근거와 함께 댓글로 달아주시면 정말 감사하겠습니다!
* 바쁜 개인 일정으로 댓글 답변이 많이 느립니다 *