Как исправить мою основную программу факторизации?

Question

Вот моя программа для вывода простой факторизации заданного числа. Я все еще просто новичок в java, поэтому я знаю, что это не самый эффективный код. Проблема возникает при вводе относительно больших чисел.

Вход: 11 Выход: 11

Вход: 40 Выход: 2 2 2 5

Вход: 5427 Выход: 3 3 3 3 67

Входной сигнал: 435843 Выход: 3 3 79 613

Input: 23456789 Output: нет (нет, кажется, бесконечный цикл и код должен возвращать 23456789, так как это простое число, само по себе)

что может CAUS Этот вопрос?

import java.util.Scanner; 

public class PrimeFactorization { 
    public static boolean isPrime(long n) { 
     boolean boo = false; 
     long counter = 0; 
     if (n == 1) { 
      boo = false; 
     } else if (n == 2) { 
      boo = true; 
     } else { 
      for (long i = 2; i < n; i++) { 
       if (n % i == 0) { 
        counter++; 
       } 
      } 
      if (counter == 0) { 
       boo = true; 
      } 
     } 
     return boo; 
    } 

    public static void primeFactorization(long num) { 
     for (long j = 1; j <= num; j++) { 
      if (isPrime(j)) { 
       if (num % j == 0) { 
        while (num % j == 0) { 
         System.out.printf(j + " "); 
         num = num/j; 
        } 
       } 
      } 
      if (num == 1) { 
       break; 
      } 
     } 
    } 

    public static void main(String[] args) { 
     Scanner scanner = new Scanner(System.in); 
     System.out.println("Enter any number:"); 
     long num = scanner.nextLong(); 
     System.out.print("Prime factorization of your number is: "); 
     primeFactorization(num); 
     scanner.close(); 
    } 
} 

Answer 1

Независимо от того, насколько эффективен код, факторизация больших чисел занимает некоторое время - так долго может показаться, что компьютер повесил трубку. Учитывая ваш код, даже скромно большие числа займут много времени.

Главное, что вы можете сделать, чтобы повысить эффективность вашего кода, чтобы отметить, что для любой пары коэффициентов числа один из них будет не более чем квадратным корнем из числа. Вы можете использовать этот факт, чтобы ограничить цикл, чтобы уменьшить порядок вашего алгоритма для O (n) до O (log n).

long sqrt = Math.sqrt(number); 

for (long i = 2; i < sqrt; i++) { 
    ... 

Есть много других вещей, которые вы можете сделать, но это изменение будет иметь наибольший эффект.

Если значение number изменяется в течение цикла (как, например, в вашем втором цикле факторизующего), вы будете, если конечно нужно пересчитать конечное значение:

for (...) 
    // if number changes 
    sqrt = Math.sqrt(number); 

Answer 2

Нет фактической ошибки - вы просто делаете очень неэффективный способ. В основном, вы проверяете каждое число от 1 до 23456789 за грубость, прежде чем делить.

Нет абсолютно никакого дела в этой проверке. Когда вы работаете с 1 по 23456789, каждый раз, когда вы обнаруживаете фактор, вы знаете, что он должен быть простым, потому что вы уже разделили все более мелкие факторы. Поэтому, если вы выполните все следующие действия, это будет работать корректно и намного быстрее.

• Извлеките метод isPrime полностью.
• Удалите строку if (isPrime(j)) { и соответствие }
• Изменить петлю так, чтобы j начинается на 2, как for(long j = 2 ; j <= num ; j++) {
• Удалить if (num == 1) { break; } от конца цикла. Это нецелесообразно.