[python/알고리즘] 소수 구하기

 

소수란?

---

1보다 큰 자연수 중에 약수가 1과 자기자신뿐인 수를 말하며

즉 양의 약수를 두 개만 가지는 자연수이다.

 ex) 2, 3, 5, 7, 11 ,,

 

1. 알고리즘 코드 구현

  
  def isPrime(num):
      for i in range(2, num):
          if num % i == 0 :
              return False
      return True
            

2. math 내장함수를 사용하여 구현

  
  # math 내장함수 사용
  import math
  def isPrime2(num):
      for i in range(2, math.floor(math.sqrt(num))+1):
          if num % i == 0 :
              return False
      return True
      

 

 

---

 

Q. 1보다 크고 100보다 작은 소수는 모두 몇 개 있는가?

 

A. 25 개 ( 위의 사용자 함수 사용 )

  
  cnt = 0
  for i in range(2,100):
      if isPrime2(i) :
          cnt +=1

  print(cnt)
    

 

 

에라토스테네스의 체란?

---

대표적인 소수 판별 알고리즘으로 소수를 빠르게 판별할 수 있다.

2부터 소수로 판별이 된 수의 배수를 모두 걸러내는 것이다.

ex) 2는 소수이므로 2의 배수인 4,6,8,10,,, False(소수가 아님)로 변경한다.

    3은 소수이므로 3의 배수인 6,9,12,15,,, False(소수가 아님)로 변경한다.

    4는 False임으로 if문 통과 ,, 

  
  def countPrime(num):
      # 리스트 초기화 : 0,1 자리는 False로 초기화, 2~100까지 True로 시작한다.
      sieve = [False, False] + ([True] * (num-1))
      count = 0
      
      # 2부터 자신의 수까지
      for i in range(2, num+1):
          if sieve[i]:  # True(소수)일 경우 카운트
              count += 1
          for j in range(i*2, num+1, i):  # ex) 2의 배수 리스트는 False로 변경 4,6,8,,,
              sieve[j] = False

      return count, sieve

  # 1부터 100까지의 소수의 갯수
  print(countPrime(100)) 
  

 

 

 

출처 : Youtube 주니온TV 아무거나연구소의 코린아, 코딩하자! with 파이썬