배수와 약수

1. 최대공약수를 구하는 알고리즘 (유클리드 호제법)

# not using math library
a = 48
b = 32
while a % b != 0:
    tmp = a % b
    a = b
    b = tmp
print(b) # print 16

# using math library
a = 48
b = 32
import math
print(math.gcd(a,b)) # print 16

 

2. 최소공배수를 구하는 알고리즘

# not using math library
a = 48
b = 32
while a % b != 0:
    tmp = a % b
    a = b
    b = tmp

print(48*32//b) # print 96

# using math library
a = 48
b = 32
import math
print(math.lcm(a,b)) # print 96

 

3. 약수를 전부 구하는 알고리즘

a = 48

dividor_set = set()

for i in range(1,int(a**1/2)+1):
    if a % i == 0:
        dividor_set.add(a//i)
        dividor_set.add(i)

print(sorted(dividor_set))

# print [1, 2, 3, 4, 6, 8, 12, 16, 24, 48]

 

4. 이항 계수를 구하는 알고리즘

# 10C2
import math
a = 10
b = 2
print(math.factorial(a)//(math.factorial(a-b)*math.factorial(b)))

# print 45