How to encode a number using its prime factors in java using arrays?

Question

I have this question I am trying to solve

I wrote this code

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

I am trying to get the number of its prime factors in a count variable and create an array with the count and then populate the array with its prime factors in the second loop.

count is 3
[2, 0, 0]

with an input of 6936. The desired output is an array containing all its prime factors {2, 2, 2, 3, 17, 17}.

Answer 1

Your count is wrong, because you count multiple factors like 2 and 17 of 6936 only once.

I would recommend doing it similar to the following way, recursively: (this code is untested)

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

Finally, call it with

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

You can also do it without recursion, I just feel it is easier.

Answer 2

Well here is a piece of code I would start with. It is not finished yet and I did not test it, but that's the way you should go basically.

// First find the number of prime factors

int factorsCount = 0;
    int originalN = n;
    while (n > 1) {
       int p = findLowestPrimeFactor(n);
       n /= p;
       factorsCount++;
    }

    // Now create the Array of the appropriate size 

    int[] factors = new int[factorsCount];

    // Finally do the iteration from the first step again, but now filling the array.
    n = originalN;
    int k = 0;
    while (n > 1) {
       int p = findLowestPrimeFactor(n);
       factors[k] = p;
       k++;
       n = n / p;
    }

    return factors;

Answer 3

Having found a factor (on increasing candidates), you can assume it is prime, if you divide out the factor till the candidate no longer is a factor.

Your problem is not repeatedly dividing by the factor.

public static int[] encodeNumber(int n) {
    if (n <= 1) {
        return null;
    }

    List<Integer> factors = new ArrayList<>();
    for (int i = 2; n != 1; i += 1 + (i&1)) {
        while (n % i == 0) { // i is automatically prime, as lower primes done.
            factors.add(i);
            n /= i;
        }
    }
    return factors.stream().mapToInt(Integer::intValue).toArray();
}

Without data structures, taking twice the time:

public static int[] encodeNumber(int n) {
    if (n <= 1) {
        return null;
    }
    // Count factors, not storing them:
    int factorCount = 0;
    int originalN = n;
    for (int i = 2; n != 1; i += 1 + (i&1)) {
        while (n % i == 0) {
            ++factorCount;
            n /= i;
        }
    }

    // Fill factors:
    n = originalN;
    int[] factors = new int[factorCount];
    factorCount = 0;
    for (int i = 2; n != 1; i += 1 + (i&1)) {
        while (n % i == 0) {
            factors[factorCount++] = i;
            n /= i;
        }
    }
    return factors;
}

Answer 4

you should correct some of your code like this.

public static int[] encodeNumber(int n) {

    int count = 0, base = n, mul = 1;

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

    n=base;

    int[] x = new int[count];

    int j = 0;

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

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