3

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!

5
  • What errors are you getting? Mar 13, 2014 at 2:53
  • One performance improvement is to limit the search space, done by having your for loop's terminating condition be when y <= m*m and not m/2.
    – hd1
    Mar 13, 2014 at 2:55
  • 2
    @hd1, that actually makes the search space bigger, I suspect you mean y <= sqrt(m), or y * y <= m.
    – paxdiablo
    Mar 13, 2014 at 3:08
  • I did, was going for m**.5. Thanks @paxdiablo
    – hd1
    Mar 13, 2014 at 3:10
  • 1
    you are writing continue after return that is unreachable statement.
    – Devavrata
    Mar 13, 2014 at 6:12

3 Answers 3

6

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.

4
  • for( y=5, k=4; ...; y += (k=6-k) ) .... :)
    – Will Ness
    Mar 13, 2014 at 6:58
  • @Will, that's a rather nifty trick. I couldn't easily google it since j k turns up quite a few pages :-) And I couldn't add it to the answer without a mathematical basis. But I think I nutted it out enough to explain it, so I've added it in. Cheers.
    – paxdiablo
    Mar 14, 2014 at 2:11
  • that's "wheel factorization" with 2-3 wheel. -- also, in this answer I tried to show its derivation, in a more visual way.
    – Will Ness
    Mar 14, 2014 at 8:52
  • If (%) is as efficient as (-), there's also the loop unrolling for( y=5,z=7; ...; y+=6, z+=6) ... which eliminates the two (-) operations at the price of one potential extra (%) check above the sqrt(n) (negligible). Indeed, maybe it should always be shown this way, not how I first mentioned it.
    – Will Ness
    Mar 14, 2014 at 9:22
1

This is what you probably want to do:

public static void main(String[] args) {

    int a;

    a = 42;

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

public static int factor(int m) {

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

And the output will be 2.

0

we need just a simple for loop like,

public static void finfFactor(int z) {
for(int x=1; x <= z; x++) {
    if(z % x == 0) {
        System.out.println(x);
    }
}

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.