Question

如何用辗转相除法求两个数的最大公约数？

Answer 1

质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数。

辗转相除法是判断两个数是否互质的，而不是应用在一个数上，是求两个数的大公约数。

辗转相除法的具体做法：用较小数除较大数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。

这是具体流程图，判断一个数是否是质数就是看它能否被除1以外的数整除。