약수와 소수

• 약수: a % n == 0일 때 a는 n의 약수

userNum = int(input('숫자 입력 = '))

if userNum != 0:
    for num in range (1, (userNum + 1)):
        if userNum % num == 0:
            print(f'{userNum}의 약수: {num}')
else:
    print('0보다 큰 정수 입력')

• 소수: a % n == 0일 때 n이 1 또는 a 뿐인 수

inputNumber = int(input('2 이상 숫자 입력: '))

for number in range(2, inputNumber + 1):
    flag = True
    for n in range (2, number): # number로 종료 숫자 지정: number - 1 (숫자 자기 자신 제외)
        if number % n == 0:
            flag = False  # n은 종료되고, 다음 번호의 number 반복 시작
            break

    if (flag):
        print(f'{number}: 소수!')
    else:
        print(f'{number}: \t\t합성수!!')

소인수와 소인수분해

약수 중 소수: 소인수

소인수분해

n = 2
searchNumbers = []

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

print(f'{searchNumbers}')

# 특정 숫자(A)에 숫자 하나(x)만 곱하면 어떤 수(B)의 제곱이 될 때, 해당 숫자(x)의 최소값을 구하라

n = 2
searchNumbers = []

while n <= inputNumber:
    if inputNumber % n == 0:
        print(f'소인수: {n}')
        if searchNumbers.count(n) == 0: #list에 있는 숫자 세기
            searchNumbers.append(n)

        elif searchNumbers.count(n) == 1:
            searchNumbers.remove(n) #list에 있는 숫자 삭제

        inputNumber /= n
    else:
        n += 1

print(f'{searchNumbers}')

최대공약수

• 최대공약수: 공통 소인수의 거듭제곱에서 지수가 작은 수를 곱함
  • ex. 공통 소인수가 2^3, 2^2일 경우 최대공약수: 4
• 공약수: 최대공약수의 약수

유클리드 호제법

x, y의 최대공약수는 y, r의 최대공약수와 같다.
r = x%y

공배수

최소공배수

(공통 소인수의 거듭제곱에서 지수가 큰 수) * (공통 아닌 수)을 모두 곱함