如何用Java数组实现数字的质因数编码？代码问题排查

Let's break down what's going wrong with your current code, then fix it to correctly capture all prime factors (including duplicates) for numbers like 6936.

What's Broken in Your Original Code #

Your logic for counting prime factors and populating the array has several critical issues:

• Counting phase (first loop):
  1. You only increment count once per prime factor, even if the factor repeats (like 2 appearing 3 times in 6936). The loop moves to the next i immediately after dividing n once, missing duplicates.
  2. The loop condition i < n causes you to miss prime factors that equal the remaining value of n (like the final 17 in 6936).
  3. You modify the original n variable during counting, which leaves a corrupted value for the second loop that tries to populate the array.
• Array population phase (second loop):
  1. There's an accidental break statement that exits the loop after the first iteration, so only the first factor gets added—leaving the rest of the array filled with default 0s.
  2. Same as the first loop, you don't handle repeated prime factors here either.

Corrected Code #

A cleaner approach is to first collect all prime factors (including duplicates) in a dynamic list, then convert that list to an array. This avoids having to pre-count factors (since the list's size gives you the count directly) and eliminates logic errors from tracking counts and array indices separately.

import java.util.ArrayList;
import java.util.List;

public class PrimeFactorEncoder {
    public static int[] encodeNumber(int n) {
        // Handle edge case: numbers < 2 have no prime factors
        if (n < 2) {
            return new int[0];
        }
        
        List<Integer> primeFactors = new ArrayList<>();
        int temp = n; // Use a temp variable to avoid modifying the original input
        
        // First handle the even prime (2) separately to optimize loops
        while (temp % 2 == 0) {
            primeFactors.add(2);
            temp /= 2;
        }
        
        // Now check odd numbers starting from 3
        for (int i = 3; i * i <= temp; i += 2) {
            // Keep dividing temp by i as long as it's divisible (captures duplicates)
            while (temp % i == 0) {
                primeFactors.add(i);
                temp /= i;
            }
        }
        
        // If temp is still greater than 2, it's a prime factor itself
        if (temp > 2) {
            primeFactors.add(temp);
        }
        
        // Convert the list to an int array
        int[] result = new int[primeFactors.size()];
        for (int i = 0; i < primeFactors.size(); i++) {
            result[i] = primeFactors.get(i);
        }
        
        System.out.println("count is " + primeFactors.size());
        return result;
    }
    
    // Optional: optimized isPrime method if you need it elsewhere
    public static boolean isPrime(int n) {
        if (n < 2) return false;
        if (n == 2) return true;
        if (n % 2 == 0) return false;
        for (int i = 3; i * i <= n; i += 2) {
            if (n % i == 0) return false;
        }
        return true;
    }
    
    public static void main(String[] args) {
        int[] output = encodeNumber(6936);
        // Prints: 2 2 2 3 17 17
        for (int factor : output) {
            System.out.print(factor + " ");
        }
    }
}

Key Improvements #

1. Dynamic collection with ArrayList: We don't need to pre-count factors—just add each prime factor (including duplicates) to the list as we find them.
2. Optimized prime checking: By handling 2 separately, we cut our loop iterations in half (only checking odd numbers after that). Using i * i <= temp instead of i < temp also reduces unnecessary checks.
3. Preserved original input: Using a temp variable keeps the original n intact, avoiding logical confusion between phases.
4. Handles remaining primes: If after processing all smaller factors, temp is still greater than 2, it's a prime factor we haven't added yet.

When you run this with input 6936, you'll get the expected output array [2, 2, 2, 3, 17, 17] and a count of 6.

内容的提问来源于stack exchange，提问作者Samuel Mideksa