<aside> 🧑‍💻 gcd : 최대 공약수

</aside>

• 유클리드 호제법을 이용하여 코드를 구성함
• 유클리드 호제법

  • 유클리드 호제법 수식

    

  • 나머지가 0이 될 때까지 계속 진행 시킴

    

# 최소 공약수 코드
def gcd(a, b):
	while b > 0:
		# a는 b가 되며, a를 b로 나눈 나머지가 0일때까지 지속 
		a, b = b, a % b
	return a

• 기본 예제 (분수의 덧셈)

• solution

<aside> ✅ lcm (최소공배수)

</aside>

• 두 수에 서로 공통되는 배수 중 가장 작은 수를 의미
• 두 수중 가장 큰 수부터 최소공배수가 될 수 있으며 두 수를 곱한 수가 최대공배수의 최대치가 된다.

def lcm(a, b):
	for num in range(max(a, b), a * b + 1):
		if num % a == 0 and i % b == 0:
			return num

• 기본 예제 : 피자 나누기(2)

• solution

<aside> ✅ 소수 (Prime number)

</aside>

• 1과 자기 자신만을 약수로 가지는 수

  • 2, 3, 5, 7

• 소수를 판별하기 위한 소수 판별 방법

  <aside> ✅ 에라토스테네스의 체

  

  위 방법은 2의 배수부터 n의 배수까지 순차적으로 삭제를 시킨 후 표 상에서 남아있는 숫자로 소수라는 것을 구분 지을 수 있는 방법이다.

  </aside>

• 알고리즘에서 이용하는 소수 판별법

  • 어떤 수 n에 대해서 2부터 그 수의 제곱근(root N)까지 나누어 떨어지는 수가 없을 경우 그 수를 소수라고 판별한다.
    • 47에 대한 예시
      1. 47을 제곱근을 취하게 되면 6.855… 의 값이 나오게 된다.
      2. 제곱근에는 소수 부분에 값을 가지고 있는 부분도 존재하기에 올림을 취해 주게 되면 2부터 7까지의 수 중 47과 나누어 떨어지는 수를 구한다.
      3. 2부터 7까지의 배수 중 47이 배수가 되는 수가 있는지 확인한다.
         • 2의 배수 : 46, 3의 배수 : 48, 4의 배수 : 2와 동일, 5의 배수 : 45, 6의 배수 : 48, 7의 배수 : 49
      4. 없기에 47은 소수이다.