[알고리즘] 수학 관련 알고리즘 Code - 에라토스테네스의 체, 유클리드 호제법

기초적인 수학적 알고리즘의 코드를 모아놓은 간단한 포스팅이다! 소수를 구하는 알고리즘과 최대공약수를 구하는 알고리즘! 

1. 에라토스테네스의 체

• 소수를 구하는 알고리즘
• 특정 배수를 지워가는 식으로 전개된다.

def era(n):   
  """
  Input : 몇까지 탐색할지 
  Output : n까지 숫자 중 소수를 포함한 리스트 
  """
  a = [False, False] + [True] * (n-1)

  primes = []
  for i in range(2, n+1):
    if a[i]:
      primes.append(i)
      for j in range(2*i, n+1, i):
        a[j] = False     # 배수를 지운다!
  return primes

2. 유클리드 호제법

• 최대공약수, 최소공배수 구하기
• 유클리드 호제법은 최대공약수를 구하는 알고리즘이다! 

def gcd(n, m): 
    """ 
    Input : 두 수 
    Output : 두 수의 최대공약수 
    """ 
    while m : 
    	n, m = m, n%m 
        return n

 

3. 관련 문제 

 1978 소수 찾기 https://www.acmicpc.net/problem/1978

1929 소수 구하기 https://www.acmicpc.net/problem/1929

2609 최대공약수와 최소공배수 https://www.acmicpc.net/problem/2609