java – 查找数字因子的方法
|
我正在尝试编写一个简单的程序,它接受一个非素数并返回它的第一个因子.我必须使用一种方法来做到这一点.我认为我非常接近正确的代码,但我仍然在我的方法中遇到变量定义问题.这是我的(目前不正确)代码：
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;
}
}
请让我知道什么是不正确的！ 解决方法
关于你的代码：
public static int factor(int m) {
for(int y=2 ; y <= m/2 ; y++) {
if(m%y==0) {
return y;
continue;
}
}
return y;
}
在最终返回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;
}
这具有使用素数的优点,因为素数的第一个因素是素数本身.而且,如果你愚蠢地传递一个负数(或少于两个,你也会得到你传入的数字.如果你想要不同的行为,你可能想要为代码添加一些额外的检查. 而且你可以更快地做到这一点,例如： 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,您将跳过三个的倍数以及两个的倍数： 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％已经通过跳过所有偶数来实现). 设置添加到2然后使用add = 6更新 – 添加是一种让它在2和4之间交替的方法： 6 - 2 -> 4 6 - 4 -> 2 正如我所说的,这可能会提高速度,特别是在模数比简单减法更昂贵的环境中,但你可能希望实际对其进行基准测试.我只是将它作为另一种可能的优化提供. （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |