Home  >  Article  >  Java  >  Java implementation example of prime factor algorithm for decomposing arbitrary input numbers

Java implementation example of prime factor algorithm for decomposing arbitrary input numbers

黄舟
黄舟Original
2017-10-18 10:22:071476browse

This article mainly introduces the Java implementation of the prime factor algorithm for decomposing any input number, involving Java mathematical operations related operating skills. Friends in need can refer to the following

The example of this article tells the Java implementation of decomposing any input number The prime factor algorithm. Share it with everyone for your reference, the details are as follows:

Decompose the prime factors of any input number:

Concept of prime factors: any composite number It can be written as the multiplication of several prime numbers. Each prime number is a factor of this composite number, which is called the decomposed prime factor of this composite number. Factoring prime factors only applies to composite numbers.

For example: 12 = 2x2x3 18 = 2 x 3 x 3, etc.

Let’s explain the idea of ​​​​this algorithm: First: we first write a function to find prime numbers; second; We make a function that decomposes prime factors, and then introduce a prime number function into it to determine whether it is a prime number;

The code is given below (for reference only):


package javastudy;
import java.util.*;
public class Testit3 {
  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int number;
    number = in.nextint();
    factor(number); //函数调用
    in.close(); //关流
  }
  static void factor(int number) {
    if(isPrime(number)) //首先进行判断是否为素数,如果是就直接输出
    {
      System.out.print(number);
    }
    for (int i = 2; i <= number - 1; i++) {
      if (number % i == 0) {
        System.out.print(i + "\t");
        int num = number / i; //进行一次分解num就要变一次!
        if (isPrime(num)) { //判断是否为素数,是的话就直接输出这个数字
          System.out.print(num);
        } else { //不是素数就继续分解
          factor(number / i); //利用函数递归的思想
        }
        // return ;
        break; //分解完了就退出
      }
    }
  }
  //判断是否为素数的函数
  static Boolean isPrime(int number) {
    for (int i = 2; i <= Math.sqrt(number); i++) {
      if (number % i == 0) {
        return false;
      }
    }
    return true;
  }
}

Run result:

The above is the detailed content of Java implementation example of prime factor algorithm for decomposing arbitrary input numbers. For more information, please follow other related articles on the PHP Chinese website!

Statement:
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn