约数

试除法找约数

说明：

Java代码模板（统计有多少个约数）：

1
2
3
4
5
6
7
8
9
10
static long solve(int a) {
		long ans = 0;
		for(int i = 1;i<=Math.sqrt(a);++i) {
			if(a%i==0) {
				++ans;
				if(a/i!=i) ++ans;
			}
		}
		return ans;
}

Java代码模板（统计质约数的个数）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import java.util.Scanner;

/**
 * https://www.acwing.com/problem/content/4661/
 * @author 长白崎
 * @class["质因数", "数论"]
 *
 */
public class Main {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);

        long n = sc.nextLong();
        System.out.println(solve(n));

    }

    static long solve(long n) {
        long ans = 0;
        for(long i=2;i<=Math.sqrt(n);++i) {
            if(n%i==0) {
                ++ans;
                while(n%i==0) {
                    n/=i;
                }
            }
        }
        if(n>1) ++ans;
        return ans;
    }

}

最大公约数

说明：

计算最大公约数,这里只展示通过递归实现。

其方法使用的是数学上的==辗转相除法==

gcd相关的概念还有裴蜀定理 ，即任意两个数的组合必定是他们gcd的倍数。同样可以推广到更多数：如果这些数的gcd是d，那么他们的组合是d的倍数，如果d不是1，那么必然有无限个数无法被组合出来。

Java代码模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import java.math.BigInteger;

/**
 * @description: 求最大公约数
 * @author 长白崎
 * @date 2023/3/30 12:33
 * @version 1.0
 */
public class GCD {

    public static void main(String[] args) {
        //测试集
        System.out.println(gcd(24,60));
        System.out.println(gcdFun(24,60));
    }


    /**
     * 计算最大公约数方式1
     * @param a 数字1
     * @param b 数字2
     * @return 返回最大公约数
     */
    public static  int gcd(int a, int b){ return (b==0) ? a : gcd(b, a%b); }

    /**
     * Java特有的一种最大公约数计算方式
     * @param a 数字1
     * @param b 数字2
     * @return 返回最大公约数
     */
    public static  int gcdFun(int a,int b){
        BigInteger a1 = BigInteger.valueOf(a);
        BigInteger a2 = BigInteger.valueOf(b);
        return  Integer.parseInt(a1.gcd(a2).toString());
    }
}

C++代码模板：

1
2
3
int gcd(int a,int b){
    return b?a:gcd(b,a%b);
}