[Python] 소수 판별 알고리즘 (기본, 제곱근, 에라토스테네스의 체)

(23.05.16)

 

 

1. 소수 판별 알고리즘 

: 숫자 n이 소수인지 아닌지 판별하기

 

1. n을 2부터 n-1 까지의 숫자들로 나눠보기

      

      

      

    
    

      <python />
    
def prime(n):
  for i in range(2, n):
    if n%i==0:
      return False
  return True

 

 

2. n의 제곱근까지의 숫자들로 나눠보기 (약수의 성질 이용)

      

      

      

    
    

      <python />
    
import math

def prime_sqrt(n):
  for i in range(2, int(math.sqrt(n))+1):
    if n%i==0:
      return False
  return True

 

 

3. 에라토스테네스의 체

      

      

      

    
    

      <python />
    
import math

def prime_era(n):
  array = [True for i in range(n+1)]
  for i in range(2, int(math.sqrt(n))+1):
    if array[i]:
      x = 2
      while i*x <= n:
        array[i*x]=False
        x += 1
  
  result = []
  for i in range(2, n+1):
    if array[i]:
      result.append(i)

  print(result)

시간복잡도: O(NloglogN)

 

 

 

 

 

참고자료: 이것이 코딩 테스트다 (나동빈)

https://github.com/ndb796/python-for-coding-test