在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

试试这个：

package bölüm05;

import java.util.Scanner;

public class B05S16 {

    public static void main(String[] args) {

        Scanner java = new Scanner(System.in);
        System.out.println("Bir tamsayı giriniz");
        int sayı = java.nextInt();
        int i = 2;

        while (sayı > 1) {
            if (sayı % i == 0) {
                sayı = sayı / i;
                System.out.print(i + ",");
            } else {
                i++;
            }
        }
        java.close();
    }
}

Answer 2

求所有因子的更好方法是求出因子的平方根

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);
   }
 }
}

---

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

我用筛子来计算素数

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);
    }
  }
}

Answer 3

你应该把数字除以：

for(int j = 2; j < a; j++){ // start dividing from 2
    if(a%j==0){
        System.out.println(j);
        a/=j; // divide a with j (there is remainder 0 because of condition)
        j ; // do j once more
    }
}