试除法求约数，试除法求约数个数

试除法求约数，试除法求约数个数

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

目录

文章目录

一、试除法求一个数的所有约数

二、试除法求一个数的所有质因数

三、约数个数之和

四、约数之和

五、代码

总结

末尾附上代码

一、试除法求一个数的所有约数

二、试除法求一个数的所有质因数

三、约数个数之和

我们也可以直接通过方法一获取所有的约数个数。但是也可以通过二获取

每个数我们都可以得到以下关系：N = p1^c1 * p2^c2 * ... *pk^ck

其中 pi(1<=i<=k) 是质数，ci(1<=i<=k) 是质数的个数，例如120可以分解为120=2^3+3^1+5^1

通过二的试除法求一个数的所有质因数，假如传入一个数120。我们可以得到，120的质数个数：

那么它的约数个数就是：(c1 + 1) * (c2 + 1) * ... * (ck + 1)-->(3+1)*(1+1)*(1+1)=16

为什么是这个公式，因为一个数的因数一定能 从它的 质因数和1 中选几个组合得到

2有4种选法（选0,1,2,3个），3有2种选法（选0,1个），5有2种选法（选0,1个），相乘即使16

映射的代码为：

四、约数之和

我们可以通过一直接求和，也可以通过二求：

一个数的约数必定可以用这个数的质因数表示出来，如120的约数30，用质因数表示就是： 2^1*3^1*5^1  即为 p1^i*...*pk^j

求约数之和的公式为：(p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)

通过分配率我们可以得到多个 p1^i*...*pk^j(0<=i<=c1 0<=pk<=ck) 相加的式子，每个p1^i*...*pk^j就是我们需要的约数

五、代码

berTheory;import java.util.*;/*** @Auther: duanYL* @Date: 2023/10/17/8:59* @Description:*/
public class Divisor {public static void main(String[] args) {getAllDivisors(120);
//        getPrimeFactor(120);
//        numberOfDivisor(120);sumOfDivisor(120);}/***   试除法求一个数的所有约数* @param n*/private static void getAllDivisors(int n) {int sum=0;ArrayList<Integer> list = new ArrayList<>();for (int i = 1; i <= n /i; i++) {if (n %i==0){sum+=i;list.add(i);    //120的约数有2和60，所以这里添加两次if (i!=n/i){list.add(n/i);//25=5*5,但是只需要添加一次5就行sum+=n/i;}}}list.sort(ComparatorparingInt(o -> o));System.out.println(list.size()+"个约数 分别是："+list +" 他们的和为："+sum);}/***  试除法 求一个数的每个质因数的个数* @param n 让 n 被每个质数循环除去 就可以得到n包含的每个质数的个数了*/private static HashMap<Integer, Integer> getPrimeFactor(int n){//用map存质数和质数的个数HashMap<Integer, Integer> factorMap = new HashMap<>();for (int i = 2; i <= n/i; i++) {/*  当i是合数的时候不会进入这个if判断i如果是合数就必定可以分解为几个质数相乘这几个质数都必定小于i，而这几个质数都在之前的while循环中除尽了*/if (n%i == 0){int count = 0;while(n%i==0){n/=i;count++;}factorMap.put(i,count);}}if (n>1) {  //满足该条件说明了，传入的n本身就是个质数factorMap.put(n,1);}for (Map.Entry<Integer, Integer> entry : Set()) {System.out.print("质因数"&#Key()+"有"+ Value()+"个 ");}return factorMap;}private static void numberOfDivisor(int n){HashMap<Integer, Integer> map = getPrimeFactor(n);int count=1;for (Integer value : map.values()) {count*=value+1;}System.out.println(count);}private static void sumOfDivisor(int n){HashMap<Integer, Integer> map = getPrimeFactor(n);int res=1;for (Map.Entry<Integer, Integer> entry : Set()) {Integer prime = Key();Integer index = Value();int sum=1;int temp=1;for (int i = 1; i <= index; i++) {temp*=prime;sum+=temp;}res*=sum;}System.out.println(res);}}

总结

只要能理解一个合数能分解为几个质因数的冥的乘积，就能理解相关的思路了