Method to find a factor of a number

Question

I am trying to write a simple program that takes a non-prime number and returns the first factor of it. I have to use a method to do this. I think that I am really close to the correct code, but I keep running into variable definition issues in my method. Here is my (currently incorrect) code:

public class testing {
    public static void main(String[] args) {

        int a;

        a = 42;

        System.out.println(factor(a));

    }

    //This method finds a factor of the non-prime number
    public static int factor(int m) {   
        for(int y=2 ; y <= m/2 ; y++) {
            if(m%y==0) {
                return y;
                continue;
            }
        }
    return y;
    }
}

Please let me know what's incorrect!

Answer 1

Regarding your code:

public static int factor(int m) {   
    for(int y=2 ; y <= m/2 ; y++) {
        if(m%y==0) {
            return y;
            continue;
        }
    }
    return y;
}

At the point of that final return y, y does not exist. Its scope is limited to the inside of the for statement since that is where you create it. That's why you're getting undefined variables.

In any case, returning y when you can't find a factor is exactly the wrong thing to do since, if you pass in (for example) 47, it will give you back 24 (47 / 2 + 1) despite the fact it's not a factor.

There's also little point in attempting to continue the loop after you return :-) And, for efficiency, you only need to go up to the square root of m rather than half of it.

Hence I'd be looking at this for a starting point:

public static int factor (int num) {   
    for (int tst = 2 ; tst * tst <= num ; tst++)
        if (num % tst == 0)
            return tst;
    return num;
}

This has the advantage of working with prime numbers as well since the first factor of a prime is the prime itself. And, if you foolishly pass in a negative number (or something less than two, you'll also get back the number you passed in. You may want to add some extra checks to the code if you want different behaviour.

---

And you can make it even faster, with something like:

public static int factor (int num) {
    if (num % 2 == 0) return 2;
    for (int tst = 3 ; tst * tst <= num ; tst += 2)
        if (num % tst == 0)
            return tst;
    return num;
}

This runs a check against 2 up front then simply uses the odd numbers for remainder checking. Because you've already checked 2 you know it cannot be a multiple of any even number so you can roughly double the speed by only checking odd numbers.

---

If you want to make it even faster (potentially, though you should check it and keep in mind the code may be harder to understand), you can use a clever scheme pointed out by Will in a comment.

If you think about the odd numbers used by my loop above with some annotation, you can see that you periodically get a multiple of three:

 5
 7
 9   = 3 x 3
11
13
15   = 3 x 5
17
19
21   = 3 x 7
23
25
27   = 3 x 9

That's mathematically evident when you realise that each annotated number is six (3 x 2) more than the previous annotated number.

Hence, if you start at five and alternately add two and four, you will skip the multiples of three as well as those of two:

5, +2=7, +4=11, +2=13, +4=17, +2=19, +4=23, ...

That can be done with the following code:

public static long factor (long num) {
    if (num % 2 == 0) return 2;
    if (num % 3 == 0) return 3;
    for (int tst = 5, add = 2 ; tst * tst <= num ; tst += add, add = 6 - add)
        if (num % tst == 0)
            return tst;
    return num;
}

You have to add testing against 3 up front since it violates the 2, 4, 2 rule (the sequence 3, 5, 7 has two consecutive gaps of two) but that may be a small price to pay for getting roughly another 25% reduction from the original search space (over and above the 50% already achieved by skipping all even numbers).

Setting add to 2 and then updating it with add = 6 - add is a way to have it alternate between 2 and 4:

6 - 2 -> 4
6 - 4 -> 2

As I said, this may increase the speed, especially in an environment where modulus is more expensive than simple subtraction, but you would want to actually benchmark it to be certain. I just provide it as another possible optimisation.