시간복잡도 - (유클리드 호제법, 에라토스테네스의 체)

유클리드 호제법

두 수 a, b가 있을 때, 서로 상대 수를 나눠서 원하는 수를 구할 수 있다.

만약 a>b이고, a%b==r이라면, 

a와 b의 최대공약수는 b와 r의 최대공약수이다.

최대공약수는 보통 gcd라 쓰는데, 

def gcd(a, b):
	while b!=0 :
    	tmp = b
        b = a%b
        a = tmp
    return a

 

이렇게 구현하면 된다.

최소공배수는 두 수의 곱/최대공약수를 하면 된다.

 

에라토스테네스의 체

소수 알고리즘을 풀 때,

시간복잡도를 줄이는 방법 중 하나.

체로 걸러내는 것.

어떻게?

 

[과정]

 - 모든 정수를 놓고,

 - 그 중 가장 작은 소수의 배수들을 모두 지운다.

 이 두 단계 반복!