최소 공배수 알고리즘

1. 소인수 분해

먼저 이 숫자의 소인수를 적어보세요. 최소 공배수는 모든 소인수를 곱한 것과 같습니다(동일한 소인수가 여러 개인 경우, 두 숫자를 비교하세요) 어떤 숫자가 더 많은 소인수를 갖고 더 많이 곱하는지)

예를 들어 45와 30의 최소공배수를 찾아보세요.

45=3*3*5

30=2*3*5

서로 다른 소인수는 2, 5, 3인데, 둘 다 소인수입니다. 45에는 3이 두 개 있고, 30에는 2가 있습니다. 단 하나의 3이므로 최소공배수를 계산할 때는 2를 3으로 곱합니다.

2. 공식 방법

두 숫자의 곱은 두 숫자의 최대공약수와 최소값의 곱과 같으므로 공배수. 즉, (a, b) × [a, b] = a × b입니다. 따라서 두 숫자의 최소 공배수를 찾으려면 먼저 최대 공약수를 찾은 다음 위 공식을 사용하여 최소 공배수를 찾을 수 있습니다.

예를 들어 [18, 20]을 찾으면 [18, 20] = 18 × 20 ¼ (18, 20) = 18 × 20 ¼ 2 = 180이 됩니다. 여러 자연수의 최소공배수를 찾으려면 먼저 두 숫자의 최소공배수를 찾은 다음 이 최소공배수와 세 번째 숫자의 최소공배수를 찾은 다음 계속해서 마지막 숫자를 찾으면 됩니다. 결국 얻은 최소 공배수는 구하는 숫자의 최소 공배수입니다.

위 내용은 최소 공배수 알고리즘의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!