摘要

本文主要讲解如何判断一个数是质数，和如何对一个数分解质因数。本文是很基础的也很重要的数学知识。

质数

质数又称为素数，是指大于1的并且除了1和它本身外，没有其他因数的自然数。

判断一个数是否是质数

假设该数为n， 我们只需要判断[2, n sqrt{n} n ]内是否有n的因子。如果有，则n为合数，否则，n为质数。 这种方法被称为试除法， 即试着除一下所有可能的因子。

试除法代码：

public static Boolean isprime(int n){
          
   
    if(n == 1) return false;
    for(int i = 2; i <= n / i; i++){
          
   
        if(n % i == 0){
          
   
            return false;
        }
    }
    return true;
}

注意：以上代码中，for循环的结束条件是 i <= n/i,相当于i <= sqrt(n)，两种写法都可以，只不过调用sqrt()函数会慢一些，因为for循环每次循环都会调用该函数。另外，不能写成i * i <= n 因为当n很接近int的最大值时，i*i可能会溢出。

分解质因数

根据算术基本定理又称唯一分解定理，对于任何一个合数， 我们都可以用几个质数的幂的乘积来表示。 即： N = p 1 k 1 ∗ p 2 k 2 ∗ . . . ∗ p n k n N = p_1^{k_1}*p_2^{k_2}*... *p_n^{k_n} N=p1k1∗p2k2∗...∗pnkn， p 1 < p 2 < . . . < p n p_1<p_2<...<p_n p1<p2<...<pn 如： 12 = 2 2 ∗ 3 12 =2^2*3 12=22∗3 20 = 2 2 ∗ 5 20 = 2^2*5 20=22∗5 30 = 2 ∗ 3 ∗ 5 30 = 2*3*5 30=2∗3∗5

接下来我们利用这个公式分解质因数。 设一个质数为p.如果n%p == 0，那么p就是n的一个质因数，接下来就是求p的指数，我们让n = n/p, 这样就从n中剔除了一个p,接着重复上述两步，直到n%p ！= 0

代码：

public static void prime(int n){
          
   
    for(int i = 2; i <= n / i; i++){
          
   
        int a = 0, b = 0;
        while(n % i == 0){
          
   
            a = i;
            n /= i;
            b++;
        }
        if(b > 0)
            System.out.println(a + " " + b);
    }
    if(n > 1) System.out.println(n + " " + 1);
}

注意：以上代码中for循环的结束条件也是i <= n / i，因为根据公式，最多只可能有一个质因数是大于 n sqrt{n} n ,因为有两个的话，乘积肯定超过n了。所以当for循环结束后判断n是否大于1，如果大于就说明有一个大于 n sqrt{n} n 的质因数。