[코딩테스트][파이썬] 소수 구하기

소수

1과 자기만으로 나누어 떨어지는 1 보다 큰 양의 정수를 의미한다. 

예) 2, 3, 5, 7, 11, 13, 17, 19 

참고 : https://terms.naver.com/entry.naver?docId=1113970&cid=40942&categoryId=32206 

소수

 

파이썬으로 구현하기

소수를 이해하기는 쉽지만 이것을 코딩으로는 옮기기 쉽지는 않다. 여러가지 방법이 있으나 가장 간단한 방법은 반복문을 이용해 숫자를 1씩 늘려가면서 나누어 떨어지는 값이 있는지 확인하는 방법이다. 

 

예제 1) 1부터 100까지 소수 구하기

n = 2
res = []
while n <= 100 :
  cnt = 0
  for i in range(1, n) :
    if n % i == 0:
      cnt += 1
      if cnt > 1 : break
  if cnt == 1 : print(n)
  n += 1

그러나 이 방법은 간단하지만 1부터 n까지의 소수를 구해야 한다면 반복 횟수는 (1+2+3+...+n)번으로 n 이 증가할 수록 반복 횟수도 증가하기 때문에 비효율적이다. (1 ~ 100,000 으로 한 결과 실행시간 126.4670 sec)

 

예제 2) 약수의 특성을 이용해서 탐색할 수의 반만 탐색하면 실행 시간을 줄일 수 있다. 예제 1로 작성한 알고리즘보다 실행시간이 빨라졌다.

import time
import math
start = time.time()

n = 2
res = []
while n <= 1000000 :
  cnt = 0
  for i in range(1, int(math.sqrt(n))+1) :
    if n % i == 0:
      cnt += 1 
      if cnt > 1 : break    
  if cnt == 1 : print(n)
  n += 1
  
print(f"{time.time()-start:.4f} 초") # 26.4315 초

 

에라토스테네스의 체

앞에서 제기된 문제를 해결하는데 에라토스테네스의 체 알고리즘을 활용하면 가장빠르고 효율적인 알고리즘을 작성할 수 있다.

참고 : https://terms.naver.com/entry.naver?docId=1179083&cid=40942&categoryId=32204 

에라토스테네스의 체

import time

start = time.time()
n = 1000000
lstN = [True for _ in range(n+1)]

for i in range(2, int(n**0.5)+1) :
  if lstN[i] == True :
    j = 2
    while i*j <= n :
      lstN[i*j] = False
      j += 1

for i in range(2, len(lstN)) :
  if lstN[i] :
    print(i)

print(f"{time.time()-start:.4f} 초") # 8.4252 초

 

예제 3개 중 구하려는 소수의 개수에 맞춰 알고리즘을 작성하면 될 것 같다.

 

참고문헌

https://blog.naver.com/sooave/222313331247

[속성 파이썬] 소수 구하기, 에라토스테네스의 체로 소수 구하기