배수와 약수

❓문제

https://www.acmicpc.net/problem/5086

❗문제 정리

약수인 경우 : num1<num2 and gcd(num1, num2)>=2
배수인 경우 : num1>num2 and num1*num2/gcd(num1,num2)==num1

📑코드

def gcd(a,b):
  if b==0:
    return a
  else:
    return gcd(b, a%b)

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

while a!=0 and b!=0:
  if a<b and gcd(a,b)>=2: #약수라면
    print('factor')
  elif a>b and (a*b)//gcd(a,b)==a: #배수라면
    print('multiple')
  else: #둘다 아니라면
    print('neither')

📝코드 설명

def gcd(a,b):
  if b==0:
    return a
  else:
    return gcd(b, a%b)

최대 공약수 구하는 gcd 알고리즘.

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

비교하려는 숫자 입력받기

while a!=0 and b!=0:
  if a<b and gcd(a,b)>=2: #약수라면
    print('factor')
  elif a>b and (a*b)//gcd(a,b)==a: #배수라면
    print('multiple')
  else: #둘다 아니라면
    print('neither')

• 테스트 케이스가 0이 마지막이라고 하였으므로, 비교하려는 숫자 a,b가 0인 경우에 종료.
• 약수인 경우 : a가 b보다 작고, 최대공약수가 2(공약수가 될 수 있는 가장 작은수)보다 크거나 같을 때
• 배수인 경우: a가 b보다 크고, 최소공배수가 a 일 경우

🎖제출 결과

💡insight