Java 查找数字的最大质因数

 Java 常见例子

目标:以有效的方式找到数字的最大素因数。

找到最大素因数是一个非常简单的概念。假设数字是 1092。1092 的所有质因数都是 2, 2, 3, 7, 13。因此，最大的质因数是 13。要找到它，可以使用以下算法:

number = num

  Step 1: If num is divisible by 2, store
  largest prime factor as 2. keep on dividing
  num until it is not divisible by 2. After
  each division, update num as num/2.

  Step 2: At this point, num must be odd.
  Starting with 3 to square root of num, if
  divisible, divide and update num, and update
  largest prime factor.

  Step 3: if the modified num is greater than
  2, update the largest prime factor with num. 

查找数字的最大质因数

下面的示例说明了上述算法。

public class MyClass {
  static long MaxPrime(long num) {
    long CurrMaxPrime = -1;

    //如果num能被2整除，则存储CurrMaxPrime
    //as 2.继续除num，直到不是
    //能被2整除，每次除完后更新
    //num 为 num/2。
    if(num % 2 == 0) {
      CurrMaxPrime = 2;
      while(num % 2 == 0){
        num = num/2;
      }
    }
    
    //此时num必须是奇数。从...开始
    //3 到 num 的平方根，如果可整除，则除以
    //更新num，并更新CurrMaxPrime
    for(long i = 3; i <= Math.sqrt(num); i += 2) {
      while(num % i == 0) {
        CurrMaxPrime = i;
        num = num/i;
      }
    }

    //如果修改后的num大于2，
    //用num更新CurrMaxPrime
    if (num > 2) 
      CurrMaxPrime = num;

    return CurrMaxPrime;
  }

  public static void main(String[] args) {
    long x, y, z;
    x = 42L;
    y = 1092L;
    z = 695467363456L;

    System.out.println("Largest prime factor of "+ x
                       + " is: "+ MaxPrime(x));
    System.out.println("Largest prime factor of "+ y
                       + " is: "+ MaxPrime(y));
    System.out.println("Largest prime factor of "+ z
                       + " is: "+ MaxPrime(z));
  }
} 

上面的代码将给出以下输出:

Largest prime factor of 42 is: 7
Largest prime factor of 1092 is: 13
Largest prime factor of 695467363456 is: 5433338777