Java 分解质因数

时间:2021-06-02 11:30:49

/**
 * PrimeFactor.java
 * @author:王超
 * 2017年3月13日
 * wangChaoPA实习工作练习.com.分解质因数.PrimeFactor
 * Copyright (c) 2007, 2016 Infopower corporation All Rights Reserved.
 */
package wangChaoPA实习工作练习.com.分解质因数;

import java.util.Scanner;

public class PrimeFactor
{
    private static Scanner input = new Scanner(System.in);

    /**
     * <p>
     * 描述:递归函数 分解数为质因数的乘积
     * </p>
     *
     * @param input
     *            要分解的数
     */
    public static void diGui(int input)
    {
        if (input <= 1)
        {
            System.out.print("无解");
        }
        else if (input == 2)
        {
            System.out.print(input);
        }
        else
        {
            for (int j = 2; j < input; j++)
            {
                // input不是质数且j是质数
                if (input % j == 0 && isPrimeNum(j))
                {
                    // 分解的质因数
                    System.out.print(j + "*");
                    // 从新赋值
                    input = input / j;
                    // 判断赋值后的input是否为质数
                    if (isPrimeNum(input))
                    {
                        System.out.println(input);
                        break;
                    }
                    else
                    {

                    }
                    // 调用递归函数
                    diGui(input);
                    break;
                }
            }
        }
    }

    /**
     * <p>
     * 描述:判断是否为质数
     * </p>
     *
     * @param n
     *            要判断的数字
     * @return
     */
    public static boolean isPrimeNum(int n)
    {
        // 默认所有的n都为质数
        boolean result = true;
        for (int j = 2; j < n; j++)
        {
            if (n % j == 0)
            {
                // 不是质数
                result = false;
                break;
            }
        }
        return result;
    }

    /**
     * 将一个正整数分解为质因数 例如9 = 3*3
     *
     */
    public static void main(String[] args)
    {
        int in = input.nextInt();
        System.out.print("分解的质因数为:" + in + "=");
        diGui(in);
        input.close();
    }
}