寻找一个数的因数的方法

Question

寻找一个数的因数的方法

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

请告诉我哪里有错误！

- freezefry

你遇到了哪些错误？ - Adam Zuckerman

一个性能改进的方法是限制搜索空间，可以通过将for循环的终止条件设置为y <= m*m而不是m/2来实现。 - hd1

2

@hd1，这实际上使搜索空间更大了，我猜你的意思是 y <= sqrt(m) 或者 y * y <= m。 - paxdiablo

我所做的是进行 'm**.5'。感谢@paxdiablo。 - hd1

1

你在 return 之后写了 continue，这是无法到达的语句。 - Devavrata

3个回答

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。

- Mohammad Najar

0

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

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

- chamzz.dot

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- paxdiablo · Accepted Answer

关于你的代码：

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时，它将返回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在评论中指出的一个巧妙的方案。

如果你考虑上面循环中使用的奇数，并进行一些注释，你会发现每隔一段时间就会得到3的倍数：

 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=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, 5, 7 存在两个连续的间隔为2，所以您需要在前面添加对3的测试，以符合“2、4、2”规则。但这可能是为了获得大约额外25%的搜索空间缩减（超过跳过所有偶数已经实现的50%）而付出的小代价。

将add设置为2，然后使用add = 6 - add进行更新，可以让它在2和4之间交替：

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

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