-1

これは私が持っているものです。それは問題を解決していますが、永遠にかかります。最後のループ 0 から 28123 を半分に分割し、何らかの方法で同時に実行して高速化し、最後に 2 つの合計を加算して最終結果を得ることができますか? 「スレッド」は役に立ちますか？コードをより速く解決するにはどうすればよいですか?

/*
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

別の Java ソリューション: (1 秒もかかりません)

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 に答える
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 に答える