-1

这就是我所拥有的。它正在解决问题，但需要永远。我可以将最后一个循环 0 到 28123 分成两半并以某种方式同时运行它们以使其更快，然后最后将两个总和相加得到最终结果吗？“线程”会有帮助吗？我该怎么做才能使代码更快地解决？

/*
A perfect number is a number for which the sum of its proper divisors is exactly equal to the number. For example, the sum of the proper divisors of 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect number.

A number n is called deficient if the sum of its proper divisors is less than n and it is called abundant if this sum exceeds n.

As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest number that can be written as the sum of two abundant numbers is 24. By mathematical analysis, it can be shown that all integers greater than 28123 can be written as the sum of two abundant numbers. However, this upper limit cannot be reduced any further by analysis even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.

Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.
 */

public class power {

    public static void main(String[] args){
        System.out.println(bigSum());
    }

    public static boolean isPerfect(int a){
        boolean perfect = false;

        int sum = 0;

        for(int i = 1; i<(a/2)+1; i++)
        {
            if (a%i == 0)
            {
                sum = sum + i;
            }
        }

        if(a == sum){
            perfect = true;
        }

        return perfect;
    }

    public static boolean isAbundant(int a){
        boolean Abundant = false;

        int sum = 0;

        for(int i = 1; i<(a/2)+1; i++)
        {
            if (a%i == 0)
            {
                sum = sum + i;
            }
        }

        if(a < sum){
            Abundant = true;
        }

        return Abundant;
    }

    public static boolean isDeficient(int a){
        boolean Deficient = false;

        int sum = 0;

        for(int i = 1; i<(a/2)+1; i++)
        {
            if (a%i == 0)
            {
                sum = sum + i;
            }
        }

        if(a > sum){
            Deficient = true;
        }

        return Deficient;
    }

    public static boolean isSumOfTwoAbundant(int a){
        boolean SumOfTwoAbundant = false;

        for(int i = 1; i<a; i++){
            if(isAbundant(i) && isAbundant(a-i)){
                SumOfTwoAbundant = true;
            }
        }
        return SumOfTwoAbundant;
    }

    public static long bigSum(){
        int sum = 0;

        for(int i = 0; i<28123; i++){
            if(!isSumOfTwoAbundant(i)){
                sum = sum + i;
                System.out.println("i: " + i + "; " + "Sum: " + sum);
            }
        }
        return sum;
    }
}
4

2 回答 2

0

您正在重新计算每次调用 isSumOfTwoAbundant 时是否每个数字 < a 都很丰富。尝试保留一份丰富的数字列表，并在找到时添加到其中。然后，您可以遍历该列表，而不是重新检查数字 < a 的丰度。就像是：

public static boolean isSumOfTwoAbundant(int a){
boolean SumOfTwoAbundant = false;
    if(isAbundant(a))
    {
        abundants.add(a);
    }

    for(int i = 0; i<abundants.length; i++) {
        for(int j = 0; j < abundants.length; j++) {
            if(a - abundants[i] == abundants[j]){
                SumOfTwoAbundant = true;
            }
        }
    }
    return SumOfTwoAbundant ;
}

private ArrayList<int> abundants;

还有很多其他方法可以让这变得更好，但 Project Euler 是关于通过经验学习这些方法。

于 2014-05-07T20:59:22.700 回答
0

另一个 Java 解决方案：（不到一秒）

static int sum_Of_Divisors(int n){
    int limit = n;
    int sum = 0;
    for(int i=1;i<limit;i++){
        if(n%i==0){
            if(i!=1){
                if(i != n/i)  sum += (i + n/i);
                else          sum += i;
            }
            else 
                sum += i;
            limit = n/i;
        }
    }       
    return sum;
}
static boolean isAbundant(int n){
    int sum = sum_Of_Divisors(n);
    return sum>n;
}
static boolean sum_of_Two_Abundant(int n, HashSet<Integer> abundant){
    for(Integer i:abundant){
        if(abundant.contains(n-i)) return true;
    }
    return false;
}
static long q23(){
    long sum = 0;
    HashSet<Integer> abundant = new HashSet<Integer>();
    for(int i=2;i<=28123;i++){
        if(isAbundant(i))
            abundant.add(i);
    }
    for(int i=1;i<=28123;i++)
        if(!sum_of_Two_Abundant(i, abundant)) sum+=i;
    return sum;
}
于 2015-08-15T00:54:45.730 回答