Python 약수, 소수, 소인수분해, 최대공약수, 최소공배수

1. 약수

• 약수란 어떤 수를 나누어떨어지게 하는 수를 말함
• 3의 약수는 1, 3이 되고, 9의 약수는 1, 3, 9가 있음

num = int(input("숫자를 입력하세요: "))

for i in range(1, (num+1)):
    if num % i == 0:
        print(i, end=" ")
        
# 실행결과
# 숫자를 입력하세요: 9
# 1 3 9

2. 소수

• 소수란 1과 자기 자신만을 약수로 하는 수 (단, 1은 제외)
• ex) 2, 3, 5, 7, 11, 13, ...

num = int(input("숫자를 입력하세요: "))

for i in range(2, (num+1)):
    flag = True

    for j in range(2, i):
        if i % j == 0:
            flag = False
            break

    if flag:
        print(f"{i}는 소수입니다.")

    else:
        print(f"{i}는 소수가 아닙니다.")
        
# 실행결과
# 숫자를 입력하세요: 10
# 2는 소수입니다.
# 3는 소수입니다.
# 4는 소수가 아닙니다.
# 5는 소수입니다.
# 6는 소수가 아닙니다.
# 7는 소수입니다.
# 8는 소수가 아닙니다.
# 9는 소수가 아닙니다.
#  10는 소수가 아닙니다.

3. 소인수

• 약수이면서 소수인 숫자를 소인수라고 함
• 20의 약수(1, 2, 4, 5, 10, 20) 중 2와 5가 소인수에 해당
• 1보다 큰 정수를 소인수만의 곱으로 나타내는 것을 '소인수분해'라고 함

num = int(input("숫자를 입력하세요: "))

n = 2

while n <= num:
    if num % n == 0:
        print("소인수: {}".format(n))
        num /= n

    else:
        n += 1
        
# 실행결과
# 숫자를 입력하세요: 129
# 소인수: 3
# 소인수: 43

4. 최대공약수

• 두 개 이상의 수 사이에서 공통된 약수를 공약수라고 함
• 12의 약수(1, 2, 3, 4, 6, 12)와 20의 약수(1, 2, 4, 5, 10, 20) 중 공통된 1, 2, 4가 공약수가 됨
• 공약수 중 가장 큰 공약수를 최대공약수로 지칭함

# 나눗셈 활용하는 경우
num_1 = int(input("1보다 큰 숫자를 입력하세요: "))
num_2 = int(input("1보다 큰 숫자를 입력하세요: "))

min_num = min(num_1, num_2)
max_gcd = 0

for i in range(1, min_num+1):
    if num_1 % i == 0 and num_2 % i == 0:
        max_gcd = i
        print(f"공약수: {i}")

print(f"최대공약수: {max_gcd}")

# 실행결과
# 1보다 큰 숫자를 입력하세요: 20
# 1보다 큰 숫자를 입력하세요: 30
# 공약수: 1
# 공약수: 2
# 공약수: 5
# 공약수: 10
# 최대공약수: 10

# 유클리드 호제법 사용하는 경우
num_1 = int(input("1보다 큰 숫자를 입력하세요: "))
num_2 = int(input("1보다 큰 숫자를 입력하세요: "))

temp_1 = num_1
temp_2 = num_2

while temp_2 > 0:
    temp = temp_2
    temp_2 = temp_1 % temp_2
    temp_1 = temp

print(f"{num_1}과 {num_2}의 최대공약수: {temp_1}")

# 실행결과
# 1보다 큰 숫자를 입력하세요: 20
# 1보다 큰 숫자를 입력하세요: 30
# 20과 30의 최대공약수: 10

5. 최소공배수

• 두 개 이상의 수에서 공통된 배수를 공배수라 함
• 3의 배수(3, 6, 9, 12, 15 ...)와 5의 배수(5, 10, 15, 20 ...) 중 15가 공배수에 해당됨
• 공배수 중 가장 작은 수를 최소공배수로 지칭함

# 두 수의 최소공배수
num_1 = int(input("1보다 큰 숫자를 입력하세요: "))
num_2 = int(input("1보다 큰 숫자를 입력하세요: "))

min_num = min(num_1, num_2)
max_gcd = 0

for i in range(1, (min_num + 1)):
    if num_1 % i == 0 and num_2 % i == 0:
        print(f"공약수: {i}")
        max_gcd = i

print(f"최대공약수: {max_gcd}")

# 두 수의 곱을 최대공약수로 나누면 최소공배수를 쉽게 구할 수 있음
min_lcm = num_1 * num_2 // max_gcd
print(f"최소공배수: {min_lcm}")

# 실행결과
# 1보다 큰 숫자를 입력하세요: 10
# 1보다 큰 숫자를 입력하세요: 12
# 공약수: 1
# 공약수: 2
# 최대공약수: 2
# 최소공배수: 60

# 세 수의 최소공배수
num_1 = int(input("1보다 큰 숫자를 입력하세요: "))
num_2 = int(input("1보다 큰 숫자를 입력하세요: "))
num_3 = int(input("1보다 큰 숫자를 입력하세요: "))

min_num = min(num_1, num_2)
max_gcd = 0

for i in range(1, (min_num + 1)):
    if num_1 % i == 0 and num_2 % i == 0:
        max_gcd = i

min_lcm = num_1 * num_2 // max_gcd

# num_1과 num_2의 최소공배수를 num_3과의 비교용 숫자로 할당
num_12 = min_lcm
min_num = min(num_12, num_3)
max_gcd = 0

for i in range(1, (min_num + 1)):
    if num_12 % i == 0 and num_3 % i == 0:
        max_gcd = i
print(f"{num_1}, {num_2}, {num_3}의 최대공약수: {max_gcd}")

min_lcm = num_12 * num_3 // max_gcd
print(f"{num_1}, {num_2}, {num_3}의 최소공배수: {min_lcm}")

# 실행결과
# 1보다 큰 숫자를 입력하세요: 6
# 1보다 큰 숫자를 입력하세요: 12
# 1보다 큰 숫자를 입력하세요: 18
# 6, 12, 18의 최대공약수: 6
# 6, 12, 18의 최소공배수: 36

*이 글은 제로베이스 데이터 취업 스쿨의 강의 자료 일부를 발췌하여 작성되었습니다.