找到数字因子的方法

Question

我正在尝试编写一个简单的程序,它接受一个非素数并返回它的第一个因子.我必须使用一种方法来做到这一点.我认为我非常接近正确的代码,但我仍然在我的方法中遇到变量定义问题.这是我的(目前不正确)代码:

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

请让我知道什么是不正确的!

Answer 1

关于你的代码:

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

在那个决赛的时候return y,y不存在.它的范围仅限于for语句的内部,因为这是您创建它的地方.这就是你得到未定义变量的原因.

在任何情况下,y当你找不到一个因子时返回是完全错误的事情,因为如果你传入(例如)47,它会给你back 24(47 / 2 + 1)尽管它不是一个因素.

在您返回后尝试继续循环也没什么意义:-)而且,为了提高效率,您只需要达到平方根m而不是一半.

因此,我将以此为出发点:

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

这具有使用素数的优点,因为素数的第一个因素是素数本身.而且,如果你愚蠢地传递一个负数(或少于两个,你也会得到你传入的数字.如果你想要不同的行为,你可能想要为代码添加一些额外的检查.

而且你可以更快地做到这一点,例如:

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

这会在2前面进行检查,然后只使用奇数进行余数检查.因为你已经检查过2你知道它不能是任何偶数的倍数所以你可以通过只检查奇数来大致加倍速度.

如果你想让它更快(可能,虽然你应该检查它并记住代码可能更难理解),你可以在评论中使用Will指出的聪明方案.

如果您考虑上面的循环使用的奇数和一些注释,您可以看到您定期得到三个的倍数:

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

当你意识到每个带注释的数字3 x 2比前一个带注释的数字多6()时,这在数学上是显而易见的.

因此,如果从5开始并交替添加2和4,您将跳过三个的倍数以及两个的倍数:

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

这可以使用以下代码完成:

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

你必须添加测试针对3前面,因为它违反了2, 4, 2规则(序列3, 5, 7有2个连续的两个缺口),但可能是一个小的代价获得大致另一个从原来的搜索空间(减少25%以上,并高于50已经通过跳过所有偶数来实现%.

设置add为2然后更新它add = 6 - add是一种让它在2和之间交替的方法4:

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

正如我所说,这可能会提高速度,特别是在模数比简单减法更昂贵的环境中,但你可能希望实际对其进行基准测试.我只是将它作为另一种可能的优化提供.