수학

나머지연산

• (A+B)%M = ((A%M) + (B%M)) % M
• (AxB)%M = ((A%M) x (B%M)) % M
• (A-B)%M = ((A%M) - (B%M) + M)%M

최대공약수 (GCD)

import sys
input = sys.stdin.readline

a,b = map(int, input().split())
g = 0

for i in range(2,min(a,b)):
    if a%i==0 and b%i==0:
        g = i

print(g)

일반적으로 생각할 수 있는 위의 방법의 시간복잡도는 O(N)이다

유클리드 호제법을 이용한 최대공약수

• a를 b로 나눈 나머지를 r이라고 했을 때, GCD(a,b) = GCD(b,r) 과 같다

• r이 0이면 그 때의 b가 최대 공약수이다

• GCD(24, 16) = GCD(16, 8) = GCD(8, 0) = 8

  # 유클리드 호제법을 이용한 최대공약수 구하기
  def gcd(a,b):
      if b == 0:
          return a
      else:
          return gcd(b, a%b)

최소공배수 (LCM)

• 두 수 a, b의 최대공약수를 g라고 했을 때
• 최소공배수 l = g*(a/g)*(b/g) 이다

진법 변환

• 10진법 수 N을 B진법으로 바꾸려면 N이 0이 될때 까지 나머지를 계속해서 구함
• B진법 수 N을 10진수로 바꾸려면 B^k을 곱하면서 더해가면 된다
  • 3진법 수 102 = 1 3^2 + 0 3^1 + 2 * 3^0 = 11
• A진법을 B진법으로 바꾸려면 A진법 -> 10진법 -> B진법 의 과정을 거친다

소수

• N이 소수가 되려면, 2보다 크거나 같고 루트N 보다 작거나 같은 자연수로 나누어 떨어지면 안된다

  import math
  
  def prime(n):
      if n < 2:
          return False
      
      for i in range(2, int(math.sqrt(n)) + 1):
          if n%i == 0:
              return False
      return True

소인수분해

• 2부터 루트N 까지 반복문을 돌면서 N을 나눌 수 없을 때까지 나눈다

  import math
  
  for i in range(2, int(math.sqrt(n))+1):
      while n%i == 0:
          print(i)
          n /= i
  if n>1:
      print(n)