Что не так с этим простым кодом факторизации в Java?

Question

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

public static ArrayList<Integer> primeFactorize(int num) { 
    ArrayList<Integer> primeFactors = new ArrayList<Integer>(); 

    for (int i = 2; i < Math.sqrt((double) num); i++) { 
     if (isPrime(i) && factor(num).contains(i)) { 
      primeFactors.add(i); 
      num /= i; 

      if (isPrime(num)) { 
       primeFactors.add(num); 
       break; 
      } 
      i = 2; 
     } 
    } 
    return primeFactors; 
} 

Он призывает двух других методов, которые я написал по имени factor() и isPrime(), которые делают именно то, что вы ожидали бы их (возвращает ArrayList факторов и либо true или false в зависимости от того, если вход первична, соответственно).

Я прошел через отладчик с num, равным 12, и он отлично работал для первого цикла, где он добавил 2 к primeFactors. Однако, когда он снова попал в верхнюю часть массива с num, равным 6, а i - 2, он вышел из цикла, как если бы i < Math.sqrt((double) num) вернулся false.

Но это не имеет смысла, потому что квадратный корень из 6 немного больше 2. Я также пробовал (double) i < Math.sqrt((double) num), но он просто сделал то же самое.

Может ли кто-нибудь увидеть, что мне не хватает? Спасибо за любые ответы.

---

EDIT: Вот мой код сейчас, спасибо за помощь! Я точно знаю, что могу сделать его более эффективным, поэтому я мог бы это сделать позже, но пока это прекрасно.

public static ArrayList<Integer> primeFactorize(int num) { 
    ArrayList<Integer> primeFactors = new ArrayList<Integer>(); 

    int i = 2; 
    while (i < Math.sqrt((double) num)) { 
     if (isPrime(i) && num % i == 0) { 
      primeFactors.add(i); 
      num /= i; 

      if (isPrime(num)) { 
       primeFactors.add(num); 
       break; 
      } 
      i = 2; 
     } 
     else 
      i++; 
    } 
    return primeFactors; 
} 

Answer 1

В вашем for цикле, секция i++ будет вызвана в конце каждого цикла. Таким образом, в вашем коде вы устанавливаете i равным 2. Затем цикл заканчивается и добавляет 1 к i, делая его равным 3. Затем происходит сравнение, а 3 больше, чем sqrt (6), поэтому цикл выходит.

Если вы хотите i быть 2 в следующей итерации, вам необходимо установить его значение, так что после запускает операцию приращение будет 2, а не перед тем; в этом случае вы должны установить его в 1. Лучшим решением было бы изменить структуру кода, поэтому это необязательно. As pointed out by biziclop, цикл while позволит вам решить, увеличивать или нет, и избежать этой проблемы.

Answer 2

Поскольку вы уже приняли ответ, я предполагаю, что ваша проблема решена. То, что я хочу отметить, заключается в том, что отлитие целых чисел до удвоений - это, как правило, плохая идея, если есть другой способ. Поэтому я хочу показать вам следующую реализацию, которая не использует арифметику с плавающей запятой. Также я думаю, что неплохо проверить, является ли num простым числом, потому что это замедляет алгоритм. Более того, если num % i == 0 имеет значение true, i всегда является простым числом, поэтому проверка isPrime(i) является излишней, а также замедляет ваш алгоритм.

List <Integer> primeFactors(int n) { 
    List<Integer> factors = new ArrayList<>(); 
    for (int i = 2; i <= n/i; ++i) { 
     while (n % i == 0) { 
      factors.add(i); 
      n /= i ; 
     } 
    } 
    if (n > 1) { 
     factors.add(n); 
    } 
    return factors ; 
}