因数怎么求

Question

如题所述

Answer 1

求因数方法如下：

1、牛顿迭代法

牛顿迭代法是一种利用微积分的方法求解函数零点或求极值的通用方法，也可运用到求因数上。根据欧几里得辗转相除法，人们可以得到n和m的最大公约数gcd（n，m）满足：gcd（n，m）=gcd（m，n%m），其中%表示求模运算符，即取余数。

利用变形后的这个结论，可以将n的所有因子分成两部分：m的倍数和不是m的倍数，其中不是m的倍数对应的所有因数都是n%m的因数，而且可以通过循环计算n%m的乘积来获得。

2、试除法

试除法是寻找质因数的一种简单快捷的方法，当然因为该方法仅考虑了质因数，因此无法计算出非质数因数，例如6，10等并不会在试验过程中被列举出来。

首先可以小于等于N/2的自然数逐一地判断它们是否能整除N。只要能整除，就知道N有一个与之对应的因数。如果没有找到任何因数，N就是一个质数，本身也是一个因数。

因数相关性质

1、整除：若整数a除以非零整数b，商为整数，且余数为零，我们就说a能被b整除（或说b能整除a），记作b|a。

2、质数（素数）：恰好有两个正因数的自然数。（或定义为在大于1的自然数中，除了1和此整数自身外两个因数，无法被其他自然数整除的数）。

3、合数：除了1和它本身还有其它正因数。

4、1只有正因数1，所以它既不是质数也不是合数。