（Java）试题 算法提高 约数个数
一、题目
（1）资源限制
内存限制：512.0MB
C/C++时间限制：1.0s
Java时间限制：3.0s
Python时间限制：5.0s
（2）输入
输入一个正整数N
（3）输出
N有几个约数
（4）样例输入
12
（5）样例输出
6
（6）样例说明
12的约数包括：1,2,3,4,6,12。共6个
二、原理与分析
（1）求约数的公式
(a1+1)*(a2+1)*(a3+1)*...*(ak+1)
（2）公式推理
- 任意一个数均可表示为以下形式(即分解质因数)：
N=p1^a1*p2^a2*p3^a3*...*pk^ak
- 例如：
24 = 2^3*3^1 即p1=1,a1=0,p2=2,a2=3,p3=3,a3=1,p4=4,a4=0...
- 同样任意一个数的约数就可以表示为以下形式：
p1^b1,p2^b2,p3^b3*,...,pk^bk
-
我们可知从b1到bk的每一种取法，都对应着N的一个不同的约数
b1有[0,a1]种选法,即a1+1种选法
…
bk有[0,ak]种选法,即ak+1种选法 -
相乘可得
一共有(a1+1)*(a2+1)*(a3+1)*...*(ak+1)种选法，每种选法对应一个约数
- 求约数个数的问题被转化为了求从b1到bk的选法
即约数的个数 = (a1+1)*(a2+1)*(a3+1)*...*(ak+1)
（3）举例分析
- 例如：对180分解质因数可得
180 = (2^2)*(3^2)*(5^1)
- 根据公式可得约数个数为
(a1+1)*(a2+1)*(a3+1)*...*(ak+1)=(2+1)*(2+1)*(1+1)=18个
- 从根本上来说：
180 = (2^2)*(3^2)*(5^1)
以2为底，指数可以选择0,1,2,三种选法
以3为底，指数可以选择0,1,2,三种选法
以5为底，指数可以选择0,1,两种选法
那么约数一共就有
3*3*2=18种选法
（4）小知识
- int范围内的整数,约数个数最多的大概是1500个，有时可以用来快速验证答案
（5）HashMap
- 由于每一个p1和b1都是一一对应的，即底数和指数时一一对应的，我们可以用HashMap来存储
- 因此需要了解Map集合的相关知识：
Map集合是一种双列集合，每个元素包含两个数据。
Map集合的每个元素的格式：key=value(键值对元素)。
Map集合也被称为”键值对集合“
键和值一一对应，一个键对应一个值，整个集合的特点是由键决定的
HashMap：元素按照键是无序，不重复，无索引，值不做要求。(与Map体系一致)
getOrDefault(key, default)：如果存在key, 则返回其对应的value, 否则返回给定的默认值
更加详细的关于HashMap的原理与使用可以看我的另一篇博客
暑期JAVA学习（13）Map集合体系
三、代码
import java.util.*;public class Main {//定义一个HashMap来对应存储所有项的底数与指数，一一对应，方便使用public static HashMap<Integer, Integer> primes = new HashMap<>();public static void main(String[] args) {Scanner sc = new Scanner(System.in);int x = sc.nextInt();//每个合数都可以写成几个质数相乘的形式,这几个质数就都叫做这个合数的质因数//此处用到的就是分解质因数的算法//用i遍历x的底数，若i为x的底数(即x%i==0)，就把i对应的指数加一，即把map的value值加一//例如8=2^3，那么map中key为2的value值就一共会加3for (int i = 2; i <= x/i; i++) {while (x % i == 0){x = x/i;//getOrDefault(key, default)如果存在key, 则返回其对应的value, 否则返回给定的默认值//这一句用getOrDefault是防止NullPointerExceptionprimes.put(i, primes.getOrDefault(i, 0) + 1);}}//如果说x被所有小于根号x的质数因子除完后，还大于1，说明剩下的一定是那个大于根号x的质因子，直接输出即可 (例如11，43这样的数)//证明：一个数x中最多包含一个大于根号x的质数因子，很好证明，如果有两个大于根号x的质数因子那么这俩相乘就大于x了，反证法成立if (x > 1){primes.put(x, primes.getOrDefault(x, 0) + 1);}//result存储最终结果long result = 1;//用i遍历每一个指数//利用求约数个数的公式：(a1+1)*(a2+1)*(a3+1)*...*(ak+1)for (Integer i:primes.values()) {result = (result * (i + 1));}System.out.println(result);}
}
去注释版
import java.util.*;public class Main {public static HashMap<Integer, Integer> primes = new HashMap<>();public static void main(String[] args) {Scanner sc = new Scanner(System.in);int x = sc.nextInt();for (int i = 2; i <= x/i; i++) {while (x % i == 0){x = x/i;primes.put(i, primes.getOrDefault(i, 0) + 1);}}if (x > 1){primes.put(x, primes.getOrDefault(x, 0) + 1);}long result = 1;for (Integer i:primes.values()) {result = (result * (i + 1));}System.out.println(result);}
}