【蓝桥云课】求正整数的约数个数

一、求正整数n的约数个数

方法一(常用算法)：从1到n逐一判断其能否整除n，若能整除n即为n的约数，否则不是n的约数。
方法二：从1到$\sqrt{n}$逐一判断是否为n的约数，当$\sqrt{n}$为n的约数时，个数加1；其余情况为约数时，个数加2。
方法三(素因子法)：
对于任意整数n（n≥1），都可以写成唯一素因子乘积的形式，即 ：
$$n=\prod _{i=1}^k{p}_i^{a_i}=p_1^{a_1}\ast p_2^{a_2}\ast ...\ast p_k^{a_k}$$
，则n的约数个数为$(a_1+1)\ast (a_2+1)\ast ...\ast (a_k+1)$

例如：36=2×2×3×3=$2^2\times 3^2$，36的约数个数为(2+1)×(2+1)=9
24=2×2×2×3=$2^3\times 3^1$，24的约数个数为(3+1)×(1+1)=8

import java.util.Scanner;public class FacOfNum {public static void main(String[] args) {Scanner sc = new Scanner(System.in);while(sc.hasNext()) {int n = sc.nextInt();System.out.printf("%d的约数有%d个\n",n,f1(n));System.out.printf("%d的约数有%d个\n",n,f2(n));System.out.printf("%d的约数有%d个\n",n,syz(n));}}/*方法一:从1到n逐一遍历判断*/public static int f1(int n) {int cnt = 0;for(int i=1;i<=n;i++) {if(n%i==0) cnt++;}return cnt;}/*方法二:从1到√n逐一遍历判断*/public static int f2(int n) {int cnt = 0;for(int i=1;i*i<=n;i++) {if(n%i==0) {if(i*i==n) cnt++;else cnt+=2;}}return cnt;}/*方法三:素因子的方法*/public static int syz(int n) {int cnt = 1;int bak = n;for(int i=2;i*i<=bak;i++) {int num = 0;while(bak%i==0) {num++;bak=bak/i;}cnt =cnt*(num+1);}if(bak>1) cnt=cnt*(1+1);//n本身为素数的情况return cnt;}
}

二、100!约数的个数

方法：采用素因子的方法统计

import java.util.Scanner;public class Fac100 {public static void main(String[] args) {int n = 100;System.out.println(facofn(n));}public static long facofn(int n) {int[] prime = new int[n+1];//prime[i]表示素数i这个因子出现的个数for(int i=2;i<=n;i++) {int bak = i;for(int j=2;j*j<=bak;j++) {while(bak%j==0) {prime[j]++;//当前bak是能整除j,有素因子j,prime[j]计数器+1bak=bak/j;}}if(bak>1) prime[bak]++;}long ans = 1;for(int i=2;i<=n;i++) ans=ans*(prime[i]+1);return ans;}
}