文章/答案/技术大牛

发布

社区首页 >问答首页 >Euler #3项目效率

问Euler #3项目效率
EN

Code Review用户

提问于 2014-10-19 09:31:36

回答 2查看 353关注 0票数 2

我想降低代码的复杂度。

问题:

13195的素因子为5、7、13和29。给定数N的最大素数是多少？

解决方案:

import java.util.Scanner;
import java.util.TreeSet;

public class Solution {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int testCases = sc.nextInt();
        for (int i = 0; i < testCases; i++) {
            int input = sc.nextInt();
            System.out.println(calculateFactors(input));

        }
    }

    public static int calculateFactors(int input) {
        TreeSet<Integer> set = new TreeSet<>();
        while (input % 2 == 0) {
            set.add(2);
            input = input / 2;
        }
        for (int i = 3; i < Math.sqrt(input); i = i + 2) {
            while (input % i == 0) {
                set.add(i);
                input = input / i;
            }
        }
        if (input > 2) {
            set.add(input);
        }
        int max = set.last();
        return max;
    }

}

java

programming-challenge

回答 2

Code Review用户

回答已采纳

发布于 2014-10-19 09:47:46

正确性：

项目Euler问题#3要求的最大素数为600851475143，并且该数字超过了int数据类型的范围。(对于此输入值，程序将异常终止。)您必须使用long代替。

在……里面

for (int i = 3; i < Math.sqrt(input); i = i + 2) { ... }

应该将<替换为<=，否则如果输入是素数的平方(如25)，则会得到错误的结果。如果将input转换为浮点数，则为了避免丢失精度，应将

for (long i = 3; i * i <= input; i = i + 2) { ... }

效率：

问题在于最大的主要因素。您的算法已经按递增顺序确定了主要因素。因此，不需要将主要因素存储在集合中才能获得其最大值。记住最后发现的素因子就足够了。

把它组合在一起：

您的函数(稍微重命名)看起来像

public static long calculateLargestFactor(long input) {
    long largestFactor = 1;
    while (input % 2 == 0) {
        largestFactor = 2;
        input = input / 2;
    }
    for (long i = 3; i * i <= input; i = i + 2) {
        while (input % i == 0) {
            largestFactor = i;
            input = input / i;
        }
    }
    if (input > 2) {
        largestFactor = input;
    }
    return largestFactor;
}

票数 5

Code Review用户

发布于 2014-10-19 12:21:15

for (int i = 3; i < Math.sqrt(input); i = i + 2) {

每次迭代都要计算sqrt，这比有用的工作(模数计算)浪费更多的时间。使用

for (long i = 3; i * i <= input; i = i + 2) {

是很好的(*)，因为乘法比除法快得多，使用类似的方法

long limit = (long) Math.ceil(Math.sqrt(input));
for (long i = 3; i <= limit; i = i + 2) {

可能会更好。

(*)注意，input在迭代过程中发生了变化，并且正确性并不明显。幸运的是，这是正确的。

我想，最快的解决方案(除了更聪明和复杂的算法)将是像上面那样使用limit并在发现除数时重新计算它。但这并不是什么大进步。

票数 2

页面原文内容由Code Review提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://codereview.stackexchange.com/questions/67201

复制

相似问题

问Euler #3项目效率
EN

问题:

解决方案:

回答 2

Code Review用户

正确性：

效率：

把它组合在一起：

Code Review用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问Euler #3项目效率EN

问题:

解决方案:

回答 2

Code Review用户

正确性：

效率：

把它组合在一起：

Code Review用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问Euler #3项目效率
EN