Write function which is return array of prime factors

Question

I have a function it returns prime factors of a number but when I initialize int array I set size.So the result consists unnecessary zeros.How can I return result array without zeros or how can I initialize array applicable size? I am not using Lists

public static int[] encodeNumber(int n){
        int i;
        int j = 0;
        int[] prime_factors = new int[j];
        if(n <= 1) return null;
        for(i = 2; i <= n; i++){
            if(n % i == 0){
                n /= i;
                prime_factors[j] = i;
                i--;
                j++;
            }
        }
        return prime_factors;
    }

Thanx!!!

possible duplicate of Delete item from array and shrink array — assylias
– assylias, Commented Jun 25, 2012 at 13:56

Ankit Khandelwal · Accepted Answer · 2012-09-10 04:24:24Z

Here is a quick way to get about the prime factors problem that I recently worked out. I don't claim it is original, but I did create it on my own. Actually had to do this in C, where I wanted to malloc only once.

public static int[] getPrimeFactors(final int i) {
    return getPrimeFactors1(i, 0, 2);
}

private static int[] getPrimeFactors1(int number, final int numberOfFactorsFound, final int startAt) {

    if (number <= 1) { return new int[numberOfFactorsFound]; }

    if (isPrime(number)) {
        final int[] toReturn = new int[numberOfFactorsFound + 1];
        toReturn[numberOfFactorsFound] = number;
        return toReturn;
    }

    final int[] toReturn;

    int currentFactor = startAt;
    final int currentIndex = numberOfFactorsFound;
    int numberOfRepeatations = 0;

    // we can loop unbounded by the currentFactor, because
    // All non prime numbers can be represented as product of primes!
    while (!(isPrime(currentFactor) && number % currentFactor == 0)) {
        currentFactor += currentFactor == 2 ? 1 : 2;
    }

    while (number % currentFactor == 0) {
        number /= currentFactor;
        numberOfRepeatations++;
    }

    toReturn = getPrimeFactors1(number, currentIndex + numberOfRepeatations, currentFactor + (currentFactor == 2 ? 1 : 2));

    while (numberOfRepeatations > 0) {
        toReturn[currentIndex + --numberOfRepeatations] = currentFactor;
    }
    return toReturn;
}

Sergey Kalinichenko · Accepted Answer · 2012-06-25 13:57:23Z

0

Allocate as many factors as you think the number may have (32 sounds like a good candidate), and then use Arrays.copyOf() to cut off the array at the actual limit:

return Arrays.copyOf(prime_factors, j);

answered Jun 25, 2012 at 13:57

Sergey Kalinichenko

729k85 gold badges1.2k silver badges1.6k bronze badges

Collectives™ on Stack Overflow

Write function which is return array of prime factors

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related