在刷 leetcode
时遇到需要求解最大的数字昰多少公约数的问题记录一下,主要有两种处理方式:
欧几里德算法
又称 辗转相除法
计算公式为
更相减损法
是出自《九章算术》的一種求最大的数字是多少公约数的算法,其思想原文为
可半者半之不可半者,副置分母、子之数以少减多,更相减损求其等也。以等數约之
第一步:任意给定两个正整数;判断它们是否都是偶数。若是则用2约简;若不是则执行第二步。
第一步只是有可能减少数字的位数简化计算。
O(N) ( N 是原先的两个数中较大的一个)