최소공배수 (1) 썸네일형 리스트형 [python] 백준 2609 : 최대공약수와 최소공배수 최대공약수를 구하는 방식엔 어떤게 있을까요? 보통은 주어진 정수를 소수의 곱으로 표현해 소수의 공통부분을 보겠지요. 예를들어 100과 50의 최대공약수를 구할때 100=2^2x5^2, 50=2x5^2로 나타낸후 두 곱의 최대 공통부분인 2x5^2를 최대공약수로 결정합니다. 이게 우리가 초등학교때 배우는 방식이지요. 그런데 만약 최대공약수를 구하는 코드를짤때도 위와같은 알고리즘이 효율적일까요? 위의 알고리즘을 사용하려면 일단 '소수'를 정의해줘야합니다. 소수를 정의해준후 입력받은 정수를 소수의 곱으로 나타내야하는데 이때 소수의 최솟값부터 검사를 해줘야겠죠. 이 과정을거쳐 두 정수가 소수의 곱으로 표현되었다면 이젠 곱의 공통영역을 구해주면됩니다. 근데 너무 비효율적인거 아닌가요? '소수'를 정의해주는 과정에.. 이전 1 다음