?? 本专栏的目的是帮助您更好地掌握和学习Java，特别是一些Java学习者网上很难找到系统的算法学习资料来帮助自己进入算法，同时对于专栏内的内容有任何疑问都可在文章末尾添加我的微信给你进行一对一的讲解。
?? 但最重要的是要独立思考。如果能完全掌握本专栏的所有内容，完全写代码，算法入门肯定没问题。
?? 算法的学习不能缺少总结。在这里，我建议你可以在大学算法社区打卡你所学的知识，以巩固和复习。
??学好算法的唯一途径一定是题海战略，只有积累大量的练习，养一种技能。我将从四个部分解释专栏中的任何主题，如主题描述解决方案模板代码代码分析。

??算术基本定理是一个非要重要的定理，它的存在是许多重要公式的基础，比如前两天我们学习的约数个数和约数之和算法。它都是建立在算术基本定理上，当时我们直接进行了质因数分解的，可能有的小伙伴还不太理解。今天我们系统来进行讲解一下

??算术基本定理课表达为：任何大于$1$的自然数$N$，如果$N$不为质数，那么$N$乘积可分解成有限数：
$$N=\prod _{i=1}^k{p}_i^{{}^i}=p_1^{a^1}\times p_2^{a^2}\times p_3^{a^3}......p_k^{a^k}(p_1,p_2....p_k均为质数)$$
  其中指数$a_i$均为正整数，这样的分解式称为$N$的标准分解式。最早是由欧几里得证明给出。 算术基本定理的证明在此我们不细讲，拓展一些基于算术基本定理可以得到的一些证明。

• $(1)$约数之和定理，$N$的所有正因数之和： $$f(N)=(p_1^0+p_1^1+...+p_1^{a_1})\ast (p_2^0+p_2^1+...+p_2^{a_2})\ast ...(p_k^0+p_k^1+...+p_k^{a_k})$$
• $(2)$对于两个整数$a$和$b$，有$a\ast b$=$gcd(a,b)\ast lcm(a,b)$
• $(3)$说明素数的个数是无限的。

  给定$n(1\le n\le 100)$个正整数$a_i(2\le a_i\le 2\ast 10^9)$，将每个数分解质因数，并按照质因数从小到大的顺序输出每个质因数的底数和指数。

• $(1)$由于需要分解多个数，所以我们将分解一个数的操作抽成一个函数进行操作
• $(2)$注意$a_i$的范围很大，我们使用long读取。

import java.util.*;

public class a { 
        
    public static void main(String[] args) { 
        
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        for (int i = 0; i < n; i++) { 
        
            long x=sc.nextLong();
            test(x);
        }
    }
    static void test(long x){ 
        
        for (int i = 2; i <=x;i++) { 
        
            if (x%i==0){ 
        
                int ans=0;
                while (x%i==0){ 
        
                    x/=i;
                    ans++;
                }
                System.out.println(i+" "+ans);
            }
        }
    }
}

但很明显我们发现，设每个数的取值范围为$m$,时间复杂达到了$O(nm)$，这是不可接收的，我们考虑对test函数进行优化

static void test(long x){ 
        
        for (int i = 2; i <=x/i;i++) { 
        
            if (x%i==0){ 
        
                int ans=0;
                while (x%i==0){ 
        
                    x/=i;
                    ans++;
                }
                System.out.println(i+" "+ans);
            }
        }
        if (x>1) System.out.println(x+" "+1);
    }

• $(1)$很明显，对于$O(m)$复杂度的test操作我们优化为$O(\sqrt{n})$。它基于的原理是对于一个正整数$n$，它的质因数中大于$\sqrt{n}$的最多只能有一个。这也很好证明，假设有两个，那么相乘肯定大于$n$了。
• $(2)$所以对于每个数$x$，我们不需要完全遍历，只需要遍历到$\sqrt{x}$的级别即可，最后判断$x$是否大于$1$，如果大于说明它此时就是那个大于$\sqrt{x}$的质因数。