Поиск всех факторов числа в 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

Вы должны разделить количество:

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

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

Гораздо более эффективным способом является использование 6 * к + - 1 правило,

Что такое 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); 
    } 
    } 
}