1

I've been asked to solve this question:

Write a function that takes two numbers n1 and n2 as input (with n2>n1) and returns an array of largest prime factors corresponding to each number between n1 and n2.

My attempt is shown below, but my code is not working properly. It is not iterating from n1 to n2. How can I get it right?

public static class A{
        static int testcase1=5;
        static int testcase2=10;

        public static void main(String args[]){
            A testInstance = new A();
            int[] result = testInstance.getLpfd(testcase1,testcase2);
            System.out.print("{");
            for (int i=0;i<result.length;i++){
                if (i>0)
                    System.out.print(",");
                System.out.print(result[i]);
            }
            System.out.println("}");
        }

        public int[] getLpfd(int n1,int n2){
            int current=0;
            int[] factors = new int[20];
            for(int j=n1;j<=n2;j++){
                for (int i = 2; i <= j; i++){
                    while(j % i == 0){
                        factors[current]=i;
                        j /= i;
                        current++;
                    }
                }
            }           
            return factors;
        }
    }
}
1
  • 1
    Well, first you're modifying your first for-loop variable (j) in the while-loop. That's not helping.
    – Gladhus
    Mar 24, 2014 at 13:01

1 Answer 1

0

It's easiest to separate the task of finding factors from the task of writing the largest factor. Here is a function to find factors:

function factors(n)
    f, fs := 2, []
    while f * f <= n
        while n % f == 0
            insert f at head of fs
            n := n / f
        f := f + 1
    if n > 1
        insert n at head of fs
    return fs

That returns the factors of n in descending order, so the largest factor is at the head of the list. Then it is easy to accumulate a list of the largest prime factors of a range:

function lpf(lo, hi)
    result := makeArray(0 .. hi-lo)
    for n from lo to hi
        result[n-lo] := head(factors(n))
    return result

I'll leave it to you to translate that to Java.

If your range is large, a variant of the Sieve of Eratosthenes will be very much faster than computing all those factors.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.