java - 如何使用数组在java中使用素数对数字进行编码？

Question

我有这个问题正在尝试解决

这段代码是我写的

public static int[] encodeNumber(int n) {
    int count = 0, base = n, mul = 1;

    for (int i = 2; i < n; i++) {
        if(n % i == 0 && isPrime(i)) {
            mul *= i;
            count++;
            if(mul == n) {
                break;
            }
            n /= i;
        }
    }

    System.out.println("count is " + count);

    int[] x = new int[count];

    int j = 0;

    for (int i = 2; i < base; i++) {
        if(n % i == 0 && isPrime(i)) {
            mul *= i;
            x[j] = i;
            j++;
            if(mul == n)    break;
            n /= i;
        }
        break;
    }

    return x;
}

public static boolean isPrime(int n) {
    if(n < 2)   return false;
    for (int i = 2; i < n; i++) {
        if(n % i == 0)  return false;
    }
    return true;
}

我试图在计数变量中获取其质因数的数量，并使用该计数创建一个数组，然后在第二个循环中用其质因数填充该数组。

count is 3
[2, 0, 0]

输入为 6936。所需的输出是一个包含其所有质因数的数组{2, 2, 2, 3, 17, 17}。

Answer 1

您的计数是错误的，因为您仅对6936的2和17等多个因子进行了一次计数。

我建议以类似于以下方式的递归方式进行操作:(此代码未经测试)

void encodeNumberRecursive(int remainder, int factor, int currentIndex, Vector<Integer> results) {
     if(remainder<2) {
         return;
     }
     if(remainder % factor == 0) {
         results.push(factor);
         remainder /= factor; 
         currentIndex += 1; 
         encodeNumberRecursive(remainder , factor, currentIndex, results);  
     } else {
         do {
            factor += 1;
         } while(factor<remainder && !isPrime(factor));
         if(factor<=remainder) {
             encodeNumberRecursive(remainder , factor, currentIndex, results); 
         }
     }
}

最后，调用它

Vector<Integer> results = new Vector<Integer>();
encodeNumberRecursive(n, 2, 0, results);

你也可以不使用递归，我只是觉得这样更容易。