java分解质因数的方法 [源代码分享]

作者: 杨圣亮 分类: Java编程 发布时间: 2016-12-17 13:49

概念:每个合数都可以写成几个质数相乘的形式。其中每个质数都是这个合数的因数,叫做这个合数的分解质因数。 质数本身已不能再分,故分解质因数只针对合数。

以下为java源码:

import java.util.ArrayList;

/**
 * 分解质因数
 * @url http://www.yangshengliang.com/biancheng-kaifa/java-jiancheng/527.html
 * @author fedkey
 * @blog www.yangshengliang.com
 *
 */

public class GetFactor {
    private static ArrayList<Integer> factorArr = new ArrayList<>(); // 存放质因数

    public static void main(String[] args) {
	long startTime = System.currentTimeMillis();
	int num = 2000000000;
	GetFactor.getFactor(num);
	// 计时
	long endTime = System.currentTimeMillis();
	System.out.print(num + "分解质因数为:\t" + factorArr);
	System.out.print("\n");
	System.out.println("GetFactor()执行耗时:" + (endTime - startTime) + "ms");

    }

    public static void getFactor(int num) {

	if (isPrime(num)) {
	    factorArr.add(num);
	}
	for (int n = 2; n <= num / 2; n++) {
	    if (isPrime(n) && num % n == 0) {
		int c = num / n;// 商
		factorArr.add(n);
		if (!isPrime(c)) {
		    getFactor(c);

		} else {
		    factorArr.add(c);

		}
		break;

	    }

	}
    }

    /**
     * 判断是否是质数
     * 
     * @param num
     * @return
     */
    public static boolean isPrime(int num) {
	int n = 2;
	boolean flg = true;
	if (num < 2) {
	    flg = false;
	}
	for (; n <= Math.sqrt(num); n++) {
	    if (num % n == 0) {
		flg = false;
	    }
	}
	return flg;

    }

}

源码分析:

1.用>=2的质数做除(相对于合数,质数毕竟是少数,避免不必要的计算)数去除,如果能除完,则该质数是该合数的一个质因数,加入到 factorArr中

2.检测商是否是质数,如果是质数,将直接放入结果集 factorArr中,程序结束;

3.如果商是合数,则再次分解(递归调用getFactor(int num)方法),直到商为质数不可再分为止。

可支持亿级的合数分解质因数,速度很快。

例中把待分解质因数的合数设置为:2000000000(20亿),耗时4毫秒,得到结果如图:

2000000000分解质因数.png

本文链接地址: java分解质因数的方法 [源代码分享]

2条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

5 × = 5

微信