Lv0 유한소수 판별하기

https://school.programmers.co.kr/learn/courses/30/lessons/120878

프로그래머스

이 문제를 풀기 전에 유클리드 호제법을 알고 있어야 하는데 유클리드 호제법이란 2개의 자연수의 최대공약수(GCD)를 구하는 알고리즘으로 2개의 자연수 a,b에 대해서 a를 b로 나눈 나머지를 r이라고 하면(단, a>b), a와 b의 최대 공약수는 b와 r의 최대공약수와 같다라는 개념이다.

그렇다면 최소공배수는 두 수의 곱을 두 수의 최대공약수로 나눈 값임을 이용하면 유클리드 호제법을 이용하여 구할 수 있다. 즉 lcm = a*b // gcd(a, b)라는 것이다.

파이썬 3.9버전에는 최소공배수를 바로 구할 수 있는 from math import lcm, lcm(a,b)가 있다. 

문제에 접근하기 위해서 gcd, 최대공약수를 사용할것이기에 from math import math를 사용한다.

유한소수를 구하는 것이기 때문에 분모에 소인수가 2와5만 존재해야 하고 a/b가 약분이 될 수 있기에 최대공약수를 이용해

b = b / gcd(a,b)로 약분을 분모에만 해준다.

그 후 2,5만 존재하는지 판단하기 위해 for i in [2,5], while b % i == 0, b = b//i를 통해 b가 2와5로 나누어지면 계속해서 나눈후 반복문이 종료 되었을 때 b가 1이라면 유한소수이므로 return 1, 아니라면 return 2를 해주면 된다.