기초 수학 - 약수, 소수, 소인수, 공약수, 공배수

약수
 어떤 수를 나누어 떨어지게 하는 수

소수
 1과 그 수 자신만을 약수로 가지는 수

 

# 파이썬을 이용한 약수 구하기 (나머지가 0인 숫자를 찾는 것이 핵심)

inputNumber = int(input('0보다 큰 정수 입력 : '))

for number in range(1, inputNumber + 1):
    if inputNumber % number == 0:
        print('{}의 약수 : {}'.format(inputNumber, number))

 

# 파이썬을 이용한 소수 구하기

inputNumber = int(input(‘0보다 큰 정수 입력: ’))

for number in range(2, (inputNumber + 1)):
    flag = True
    for n in range(2, number):
        if number % n == 0:
            flag = False
            break

    if (flag):
        print(‘{} : 소수’.format(number))
    else:
        print(‘{} : 합성수’.format(number))

 

소인수
 소인수란 약수(인수) 중에서 소수인 숫자를 소인수라고 한다. 소인수분해란 1보다 큰 정수를 소인수의 곱으로 나타낸 것이다. 예를 들어 12의 소인수분해는 2^2 x 3이고, 25의 소인수분해는 5^2이며, 41의 소인수분해는 41이다. 소인수분해를 이용하면 약수를 정확하고 쉽게 구할 수 있다.

 

# 파이썬을 이용하여 소인수분해

inputNumber = int(input('1보다 큰 정수 입력 : '))

n = 2
while n <= inputNumber:
    if inputNumber % n == 0:
        print('소인수 : {}'.format(n))
        inputNumber /= n
    else:
        n += 1

 

공약수
 공약수란 두 개 이상의 수에서 공통된 약수이다. 최대공약수란 공약수 중 가장 큰 수를 뜻한다. 소인수분해를 이용하면 공약수 및 최대공약수를 구할 수 있다. 그러나 두 수를 더이상 나눌 수 없을 때까지 나눈 후 몫을 모두 곱하면 최대공약수를 편리하게 구할 수 있다.

 

# 파이썬을 이용하여 공약수와 최대공약수 구하기

num1 = int(input('1보다 큰 정수 입력 : '))
num2 = int(input('1보다 큰 정수 입력 : '))
maxNum = 0

for i in range(1, num1+1):
    if num1 % i == 0 and num2 % i == 0:
        print('공약수 : {}'.format(i))
        maxNum = i
print('최대공약수 : {}'.format(maxNum))

최대공약수는 유클리드 호제법을 이용하여 구할 수도 있다. 유클리드 호제법이란 x와 y, 두 개의 숫자와 x % y의 값인 r이 있다고 할 때, 첫 번째 식에서는 x % y = r, 두 번째 식에서는 y % r = r1, 세 번째 식에서는 r % r1 = r2처럼 계속해서 y를 x 자리로, r을 y자리로 옮겨서 나머지인 r 값이 0이 될 때까지 나눗셈하는 계산법이다. 여기서 마지막 식의 y는 최대공약수이다.

 

공배수
 두 개 이상의 수에서 공통된 배수를 공배수라 하고, 그 중 가장 작은 공배수를 최소공배수라 한다. 공배수 및 최소공배수는 소인수분해를 이용하여 공통된 소인수의 거듭제곱에서 지수가 크고 공통이 아닌 수를 모두 곱하여 구할 수도 있지만, 더이상 몫이 나오지 않을 때까지 나눗셈을 한 다음, 몫과 나머지를 모두 곱하면 더 편리하게 최소공배수를 구할 수 있다.

 

# 파이썬을 이용하여 최소공배수 구하기

num1 = int(input('1보다 큰 정수 입력 : '))
num2 = int(input('1보다 큰 정수 입력 : '))
maxNum = 0

for i in range(1, num1+1):
    if num1 % i == 0 and num2 % i == 0:
        print('공약수 : {}'.format(i))
        maxNum = i

print('최대공약수 : {}'.format(maxNum))

minNum = (num1 * num2) // maxNum

print('최소공배수 : {}'.format(minNum))