소수 판별

소수(prime number)인지 판별하는 기본 알고리즘

# 시간복잡도 : O(N ** 0.5)
def is_prime(n):
	if n < 2:
		return False
	
	for i in range(2, int(n**0.5)+1):
		if n % i == 0:
			return False
	return True

에라토스테네스의 체

다수의 소수를 빠르게 구하는 방법

# 시간복잡도 : O(N * log(logN))
def eratosthenes(n):
	is_prime = [True] * (n+1) # 0 ~ n
	is_prime[0], is_prime[1] = False # 0,1은 소수X
	
	for i in range(2, int(n ** 0.5)+1):
		if is_prime[i] == True:
			for j in range(i*i, n+1, i):
				is_prime[j] = False
	
	return [i for i,val in enumerate(is_prime) if val]

최대공약수(GCD)

두 수 a, b의 공통 약수 중에서 가장 큰 값

유클리드 호제법

두 수의 최대공약수(GCD)를 구하는 대표적인 알고리즘

# 반복문
def gcd(a,b):
	while b != 0:
		a,b = b, a%b
	return a

# 재귀함수
def gcd(a,b):
	return b != 0 ? gcd(b, a%b) : a

추가 설명

두 수 a,b가 있을 때 우리는 $a = bq + r(0<=r<b, a>b)$ 라고 할 수 있습니다. 이때 어떤 수 d가 a,b의 공약수라고 생각해볼게요. 그렇다면 $a - bq = r$ 에 대해서 d로 양변을 나눌 수 있습니다.

$a = bq + r$ 과 $r = -bq + a$ 를 같이 살펴볼까요? 비슷하다는 느낌을 받으실 겁니다. 맞습니다. **a,b의 공약수가 있다를 나타내는 GCD(a,b)**는 **b,r의 공약수가 있다를 나타내는 GCD(b,r)**과 동일하다는 겁니다.

좀 더 수학적으로 말하자면,

$$ d | a이고 d|b라면, d|(a-bq) = r이다. 따라서 d|r이고 d|b, 즉 d는 gcd(b,r)의 공약수이다 $$

결론을 말하자면, **GCD(a,b) == GCD(b,r)**이 되는거죠.

최소공배수(LCM)