숫자 N이 주어졌을때 1부터 N까지의 소수를 모두 구하는 함수를 작성해보겠습니다.
단순하게 생각해보기
단순하게 모든 숫자를 순회하며 1을 제외한 수로 나눠지는지 ( 소수는 1와 자신을 제외한 수로 나누어지지 않는 수이므로) 확인하는 방법.다만 모든 수를 다 나눠볼 필요는 없고, 자신의 절반 값까지만 확인해보면된다.왜냐하면 자신의 절반 보다 큰 수는 x2를 하면 자신보다 큰 값이 나오기 때문이다. ( 예) 10/2 = 5, 5×2 = 10 이지만 6×2=12 )
def get_prime_nums1(n):
prime_nums = []
for i in range(2, n + 1):
flag = 1
for j in range(2, i // 2 + 1):
if i % j == 0:
flag = 0
break
if flag == 1:
prime_nums.append(i)
return prime_nums
if __name__ == '__main__':
print(get_prime_nums1(10)) # [2, 3, 5, 7]최적화 하기
단순하게 순회하면 자신보다 작은 수로 나눠보는 방법은 단순한만큼 숫자의 범위가 커질수록 느립니다. 그래서 좀 더 빠르게 구하기 위해 최적화를 해보겠습니다.
def get_prime_nums2(n):
sieve = [True] * (n+1)
for i in range(2, int(n ** 0.5) + 1):
if sieve[i]:
for j in range(i + i, n+1, i):
sieve[j] = False
return [i for i in range(2, (n+1)) if sieve[i]]
if __name__ == '__main__':
print(get_prime_nums2(10)) # [2, 3, 5, 7]해당 함수는 에라토스테네스의 체를 구현한 함수인데요.( 해당 원글의 python 코드는 n 값이 5, 6인 경우에 처리가 정상적으로 안되는 문제가 있어서 일부 코드를 수정했습니다. )에라토스테네스의 체의 알고리즘은 아래와 같습니다.2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. – 자기 자신을 제외한 2의 배수를 모두 지운다.– 남아있는 수 가운데 3은 소수이므로 자기 자신을 제외한 3의 배수를 모두 지운다.– 남아있는 수 가운데 5는 소수이므로 자기 자신을 제외한 5의 배수를 모두 지운다.– 남아있는 수 가운데 7은 소수이므로 자기 자신을 제외한 7의 배수를 모두 지운다.위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.우선 함수를 실행하면 인자로 받은 숫자범위만큼 True로 정의한 리스트를 생성합니다.( 이 리스트의 True False 를 토대로 소수여부를 판단합니다. True => 소수 )그리고 2부터 n의 제곱근까지 루프를 돌면서 각 수의 배수를 False로 변경해줍니다.모든 루프가 종료 된 후 True 인 요소들의 index를 리스트로 만들어서 리턴하여 소수의 리스트를 반환합니다.
속도 비교
import time
def get_prime_nums1(n):
prime_nums = []
for i in range(2, n + 1):
flag = 1
for j in range(2, i // 2 + 1):
if i % j == 0:
flag = 0
break
if flag == 1:
prime_nums.append(i)
return prime_nums
def get_prime_nums2(n):
sieve = [True] * (n+1)
for i in range(2, int(n ** 0.5) + 1):
if sieve[i]:
for j in range(i + i, n+1, i):
sieve[j] = False
return [i for i in range(2, (n+1)) if sieve[i]]
if __name__ == '__main__':
start = time.time()
get_prime_nums1(10000)
print("get_prime_nums1:", time.time() - start)
start = time.time()
get_prime_nums2(10000)
print("get_prime_nums2:", time.time() - start
# get_prime_nums1: 0.22524499893188477
# get_prime_nums2: 0.0014650821685791016이상으로 소수를 구하는 방법에 대해 알아보았습니다.감사합니다. 😄