유클리드호제법

[알고리즘] 수학 관련 알고리즘 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. 유클리드 호제법 최대공약수, 최소공배수 구하기 유클리드 호제법은 최대공약수를 구하는 알..