Testing if a number inside an Array is a duplicate and then removing it

Question

So my Problem is i have to list the prime factors of a number inside an Array and the power of that prime factor in another one on the same positions inside their given array(so if you want the primefactors of 60 i would need to return an array with contents like this: primes: {2, 3, 5} powers {2, 1, 1} => (2*2)*(3*1)*(5*1) = 60. I now have the following code to determine the duplicates inside the primes Array but how can i now instead of printing them to the console save them in another variable to then use them for the powers Array?

long current = primes[0];
boolean found = false;
for( int i = 0; i < primes.length; i++) {
   if( current == primes[i] && !found) {
      found = true;
   }
   else if( current != primes[i] ) {
      System.out.print(" " + current);
      current = primes[i];
      found = false;
   } 

The full code would then be:

public class Algebra {

public static long [][] primfaktorzerlegung(long n){

    int position = 0;
    long[] primes = new long [0];
    long [] powers = new long [0];



    while(n%2 == 0) {
        primes[position] = 2;
        position++;
        n = n / 2;
    }
    for (int i = 3; i <= Math.sqrt(n); i+= 2)
    {
        while (n%i == 0)
        {

            n /= i;
        }
    }
    long current = primes[0];
    boolean found = false;
    for (int i = 0; i < primes.length; i++) {
        if (current == primes[i] && !found) {
            found = true;
        } else if (current != primes[i]) {
            current = primes[i];
            found = false;
        }


    }
    long[][] z = {primes,powers};
    return z;
    }
}

It's obviously unfinished but to show the whole thing i post it anyways.

Answer 1

You want the frequency of each prime, and there’s a standard way to do this in java. Also, since you don’t know how many primes there will be you’re better to use a List.

But you don’t even need to use either of those, just use a Map<Long, Long> and accumulate both primes and powers in one pass:

Map<Long, Long> primePowers = new LinkedHashMap<>();
for (int i = 2; i <= Math.sqrt(n); i+= 2) {
    while (n%i == 0) {
        primePowers.put(i, primePowers.getOrDefault(i, 0L) + 1);
        n /= i;
    }
}

// convert the Map to the return value
long[] primes, powers = new long[primePowers.size()];
int i = 0;
for (Map.Entry<Long, Long> entry : primePowers.entrySet()) {
    primes[i] = entry.getKey();
    powers[i] = entry.getValue();
}

return new long[][]{primes,powers};

FYI a LinkedHashMap iterates over its entries in insert order.

As a design point, the return type long[][] is not a good choice. Any situation where 2 arrays must agree on their elements aligning is poor design.

Answer 2

Code:

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

public class Primes {

   static long getPowerOf( long power, long n, List<Long> primes, List<Long> powers ) {
      if(( n % power ) == 0 ) {
         long count = 0L;
         while(( n % power ) == 0 ) {
            ++count;
            n = n / power;
         }
         primes.add( power );
         powers.add( count );
      }
      return n;
   }

   static long[][] getPrimes( long n ) throws Exception {
      final List<Long> primes = new ArrayList<>();
      final List<Long> powers = new ArrayList<>();
      n = getPowerOf( 2, n, primes, powers );
      for( long i = 3; n > 1; i += 2 ) {
         n = getPowerOf( i, n, primes, powers );
      }
      if( n > 1 ) {
         throw new Exception( "More primes needed" );
      }
      final long[][] result = new long[2][];
      result[0] = new long[primes.size()];
      result[1] = new long[powers.size()];
      for( int i = 0; i < primes.size(); ++i ) {
         result[0][i] = primes.get( i );
      }
      for( int i = 0; i < powers.size(); ++i ) {
         result[1][i] = powers.get( i );
      }
      return result;
   }

   static void showPrimes( long[] primes, long[] powers ) {
      boolean tail = false;
      for( int i = 0; i < primes.length; ++i ) {
         if( powers[i] > 0 ) {
            if( tail ) {
               System.out.print( " + " );
            }
            else {
               tail = true;
            }
            System.out.print( primes[i] + "x" + powers[i]);
         }
      }
      System.out.println();
   }

   public static void main( String[] args ) throws Exception {
      final long[][] result = getPrimes( 2*2*3*5*5*7*23*23*23 );
      showPrimes( result[0], result[1] );
   }
}

Output:

2x2 + 3x1 + 5x2 + 7x1 + 23x3

Notes:

Using a class in place of long[][] for primes and powers will be better, like this:

class PrimeUsage {
   long prime;
   long power;
}

PrimeUsage[] or List<PrimeUsage> or Set<PrimeUsage>