java - 在 Java 中找到一个数字的所有因子？

Question

“编写一个程序，读取一个整数 I 并按升序显示它的所有最小因子。例如，如果输入整数为 120，则输出应如下所示:2, 2, 2, 3, 5。” .在程序开始时，用户必须输入一个整数来标识有多少数字将被因式分解。

import java.util.Scanner;

public class Main {

    public static void main(String [] args){

        Scanner input = new Scanner(System.in);

        int size = input.nextInt();

        for(int i = 0; i < size; i++){

            int a = input.nextInt();

            for(int j = 0; j < a; j++){
                if(a%j==0){
                    System.out.println(j);
                }
            }

        }
        input.close();

    }

}

Answer 1

找到所有因数的更好方法是找到因数直到它的平方根。

int n = 120;

for(int i = 2; i * i <= n; ++i)//check below it's square root i <= sqrt(n)
 if(n % i == 0){ 
  while(n % i == 0)
  {
  System.out.println(i);
  n /= i;
  }
 }

一种更有效的方法是使用质数。

除了 2 之外不可能有任何其他素数，所以我们可以跳过偶数部分

int n = 120;

if(n % 2 == 0)
{
 while(n % 2 == 0)
 {
    System.out.println("2");
    n /= 2;
 }
}
for(int i = 3; i * i <= n; i += 2)//odd numbers only
{
 while(n % i == 0)
 {
    n /= i;
    System.out.println(i);
 }
}

A much more efficient way is to use 6*k +- 1 rule,

什么是 6*k +- 1 规则？

所有质数(2和3除外)都可以用上面的公式表示。虽然反过来可能不是真的，考虑 6*6 - 1 = 35 可被 5 整除。

如果它不是质数，它的质因数将小于它的平方根。

所以我们只检查符合上述规则的数字。

int i = 1, n = 120;
//check for 2 and 3
if(n % 2 == 0)
{
   while(n % 2 == 0)
   {
      System.out.println("2");
     n /= 2;
   }
}
if(n % 3 == 0)
{
   while(n % 3 == 0)
   {
      System.out.println("3");
      n /= 3;
   }
}
while(true)
{
   int p = 6 * i - 1;
   if(p * p > n)
      break;
   if(n % p == 0)
   {
      while( n % p == 0)
      {
        n /= i;
        System.out.println(p);
      }
   }
 p = 6 * k + 1;
 if(p * p > n)
  break;
 if(n % p == 0)
 {
   while( n % p == 0)
   {
     n /= i;
     System.out.println(p);
   }
 }
}

---

如果数字非常大而且数量很多，预先计算素数会很有帮助

我使用 Sieve 来计算素数。

int max = 10000007;
boolean[]primes = new boolean[max];
int []nums = new int[max];
int numOfPrimes = 0;

for(int i = 2; i * i < max; ++i)
 if(!primes[i])
 for(int j = i * i; j < max; j += i)//sieve
  primes[j] = true;
for(int i = 2; i < max; ++i)
 if(!primes[i])
  nums[numOfPrimes++] = i;//we have all the primes now.

int n = 120;

for(int i = 0; i < numOfPrimes; ++i)
{
  int p = nums[i];
  if(p * p > n)
   break;
  if(n % p == 0)
  {
   while(n % p == 0)
   {
    n /= p;
    System.out.println(p);
    }
  }
}