3

我正在尝试编写一个简单的程序，它接受一个非质数并返回它的第一个因子。我必须使用一种方法来做到这一点。我认为我真的很接近正确的代码，但我在我的方法中不断遇到变量定义问题。这是我的（当前不正确的）代码：

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

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

4

3 回答 3

6

关于您的代码：

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

在那个 final 的点上return y，y不存在。它的范围仅限于for语句的内部，因为这是您创建它的地方。这就是为什么你得到未定义的变量。

在任何情况下，y当你找不到一个因素时返回是完全错误的事情，因为如果你传入 (例如) 47，它会给你返回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;
}

这也具有处理素数的优点，因为素数的第一个因素是素数本身。而且，如果您愚蠢地传入一个负数（或小于 2 的数字，您也会取回您传入的数字。如果您想要不同的行为，您可能需要在代码中添加一些额外的检查。

你可以让它更快，比如：

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比前一个带注释的数字多六 ( ) 时，这在数学上是显而易见的。

因此，如果您从 5 开始并交替添加 2 和 4，您将跳过 3 的倍数以及 2 的倍数：

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有两个连续的间隙），但这可能是一个很小的代价，可以从原始搜索空间再减少大约 25%（超过 50 % 已经通过跳过所有偶数来实现）。

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

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

正如我所说，这可能会提高速度，尤其是在模数比简单减法更昂贵的环境中，但您需要实际对其进行基准测试以确定。我只是提供它作为另一种可能的优化。

于 2014-03-13T02:55:44.907 回答
1

这可能是您想要做的：

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

输出将是2.

于 2014-03-13T02:54:59.420 回答
0

我们只需要一个简单的 for 循环，例如，

public static void finfFactor(int z) {
for(int x=1; x <= z; x++) {
    if(z % x == 0) {
        System.out.println(x);
    }
}
于 2017-09-09T03:13:19.603 回答