java编程实现求质数与因式分解代码分享

下面是 "Java编程实现求质数与因式分解代码分享" 的完整攻略。

介绍

本文将介绍Java编程实现求质数与因式分解的代码。当我们需要判断一个数是不是质数时，我们可以使用质数的定义：只有1和该数本身能够整除它，它才是质数。因式分解是指将一个数分解成几个互质的整数乘积的形式。这里我们使用两种算法实现求质数：暴力算法、埃氏筛法以及一种算法实现因数的分解。

求质数的代码实现

暴力算法

暴力算法是从2开始枚举所有比目标数小的正整数，逐一判定是否为目标数的因数，时间复杂度为O(N)。

public static boolean isPrime(int n) {
    if (n <= 1) {
        return false;
    }
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

埃氏筛法

埃氏筛法是一种筛选法，它的思想是从小到大枚举每个质数，将质数的倍数都标记成合数，以此类推，直到枚举完所需范围的所有数，时间复杂度为O(N*log(log(N)))。

public static boolean[] sieveOfEratosthenes(int n) {
    boolean[] primes = new boolean[n + 1];
    Arrays.fill(primes, true);
    primes[0] = false;
    primes[1] = false;
    for (int i = 2; i * i <= n; i++) {
        if (primes[i]) {
            for (int j = i * i; j <= n; j += i) {
                primes[j] = false;
            }
        }
    }
    return primes;
}

因式分解的代码实现

public static List<Integer> factorize(int n) {
    List<Integer> factors = new ArrayList<>();
    for (int i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            factors.add(i);
            n /= i;
        }
    }
    if (n > 1) {
        factors.add(n);
    }
    return factors;
}

示例说明

示例1：求100内的质数

boolean[] primes = sieveOfEratosthenes(100);
for (int i = 0; i <= 100; i++) {
    if (primes[i]) {
        System.out.println(i);
    }
}

输出结果：

示例2：将20分解为质因数的乘积

List<Integer> factors = factorize(20);
System.out.println(factors);