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

[What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173) — Andy Turner, Jan 30 '20 at 13:50
What is your actual question? You didn't really ask one (summarizing the entire problem in the title is not a question). — Nexevis, Jan 30 '20 at 13:55
It is actually to write a function named encodeNumber that accepts an integer n and that returns an array that holds the numbers prime factors in the array in descending order. — Samuel Mideksa, Jan 30 '20 at 13:57
@SamuelMideksa that's the question that's been asked of you; what's the question you need *us* to answer to help you solve it? (BTW, your desired factors are in ascending order). — Andy Turner, Jan 30 '20 at 13:58
why is the first for loop returning count as a 3 where it should be 6 counting the duplicates also? — Samuel Mideksa, Jan 30 '20 at 14:00
@AndyTurner well my question is how can I improve the code to get the array with all number's prime factors including the duplicates? — Samuel Mideksa, Jan 30 '20 at 14:04
@SamuelMideksa did you try [debugging the code](https://stackoverflow.com/q/25385173)? If so, where did you find the code behaving in a way you didn't expect? — Andy Turner, Jan 30 '20 at 14:05
I suggest you store your factors into a list so you don't have to pre-process the number in order to know the size of the array. Beside you will want to nest two loops : a first one that increments a number until it's a prime and a second that divides your input number by that number as long as your number is divisible by it — Aaron, Jan 30 '20 at 14:06
First: after the first loop you must reset the variables. Second: change the for-loops to while loops. Else you miss the repeated primefactor 2. Third: throw away the variable mul. you don't need it. — Ralf Renz, Jan 30 '20 at 14:07
No, I did mean List, it would have made for a simpler solution — Aaron, Jan 30 '20 at 14:37

score 2 · Answer 1 · answered Jan 30 '20 at 14:18

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.

I am not allowed to use any data structures. Only arrays. Your code works though. Thanks — Samuel Mideksa, Jan 30 '20 at 14:21
With arrays, you end up with a cludge of defining a very big array, like int[log2 n] beforehand, and then copying the data from one array to another that has the minimal size. It is doable though. — Adder, Jan 30 '20 at 14:24

score 1 · Accepted Answer · edited Feb 03 '20 at 11:07

1

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;

edited Feb 03 '20 at 11:07

Samuel Mideksa

423
8
19

answered Jan 30 '20 at 14:15

DanielBK

892
8
23

Assuming `public static int findLowestPrimeFactor(int n) { for (int i = 2; i < n; i++) { if(n % i == 0 && isPrime(i) == 1) return i; } return 0; }` I am getting this division by zero somehow p is 0 when it tries to compute the division in the first loop – Samuel Mideksa Feb 03 '20 at 07:30
Hm .. maybe something is wrong with your isPrime() method? In your question the isPrime() method does return a boolean, but here you compare its result to the integer 1. Does it really return 1 for a prime argument i? I would recheck this method first. Besides this your implementation of findLowestPrimeFactor() looks ok. – DanielBK Feb 03 '20 at 08:21
Well I have changed findLowestPrimeFactor to `public static int findLowestPrimeFactor(int n) { for (int i = 2; i < n; i++) { if(n % i == 0 && isPrime(i) == 1) return i; } return n; }` and isPrime to `public static int isPrime(int n) { if(n < 2) return 0; for (int i = 2; i < n; i++) { if(n % i == 0) return 0; } return 1;` and an array with size 6 is returned the error is gone but couldn't pupulate the array with its prime factors. – Samuel Mideksa Feb 03 '20 at 10:21
Oh I just solved it the problem is n gets to 0 in the beginning of the second while loop. So I have to set it to Original N before beginning the second loop. thanks @DanielBK – Samuel Mideksa Feb 03 '20 at 10:31

score 1 · Answer 3 · answered Jan 30 '20 at 14:16

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

what is `for (int i = 2; n != 1; i += 1 + (i&1)) {` doing specifically `i += 1 + (i & 1)` a little difficult to understand. — Samuel Mideksa, Jan 31 '20 at 06:56
The last causes 2->3->5->7->9->11->..., increment at least 1 + if odd 1. — Joop Eggen, Jan 31 '20 at 08:20

score 0 · Answer 4 · answered Apr 14 '23 at 09:58

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

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

4 Answers4