Java – method of finding numeric factors

I'm trying to write a simple program that accepts a non - prime number and returns its first factor I must use a method to do this I think I'm very close to the correct code, but I still encounter variable definition problems in my methods This 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 is wrong!

Solution

About 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;
}

When y is finally returned, y does not exist Its scope is limited to the inside of the for statement, because this is where you create it That's why you get undefined variables

In any case, returning y when you cannot find a factor is completely wrong, because if you pass in (for example) 47, it will give you back 24 (47 / 21), although it is not a factor

There's no point in trying to continue the loop after you return: -) and to improve efficiency, you only need to reach the square root of M instead of half of it

Therefore, I will take this as the 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 using prime numbers, because the first factor of prime numbers is the prime number itself Moreover, if you foolishly pass a negative number (or less than two), you will also get the number you pass in. If you want different behavior, you may want to add some additional checks to the code

And you can do it faster, for example:

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 checks the previous 2, and then checks the remainder with only odd numbers Because you've checked 2, you know it can't be any multiple of even numbers, so you can roughly double the speed by checking only odd numbers

If you want to make it faster (maybe, although you should check it and remember that the code may be more difficult to understand), you can use the smart scheme pointed out by will in the comments

If you consider the odd number of recycling and some comments above, you can see that you get three multiples regularly:

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

This is mathematically obvious when you realize that each annotated number is six (3 x 2) more than the previous annotated number

Therefore, if you start with 5 and add 2 and 4 alternately, you will skip multiples of three and multiples of two:

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

This can be done using 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 must add a test before 3 because it violates the 2,4,2 rule (sequence 3,5,7 has two consecutive gaps), but this may be a small cost to reduce by about 25% from the original search space (more than 50% has been achieved by skipping all even numbers)

Add settings to 2 and update with add = 6 – adding is a way to alternate between 2 and 4:

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

As I said, this may increase speed, especially in an environment where modulus is more expensive than simple subtraction, but you may want to actually benchmark it I just offer it as another possible optimization