3

我在 python 中找到了问题 21 的解决方案，它给出了正确的答案。我尝试了其他人的 java 代码，对于 10000 和 100000 的值，我得到了相同的答案，但是当尝试 1000000 时，我的代码返回的解决方案与 java 代码返回的其他两个解决方案不同，即使返回的所有三个解决方案都是相同的测试值 10000 和 1000000 和 50000。有人有任何想法吗？

我的 Python 代码

def amicable_pairs(n):
    """returns sum of all amicable pairs under n. See project euler for 
    definition of an amicable pair"""
    div_sum = [0]*n
    amicable_pairs_set = [0]*n
    for i in range(1, n):
        for j in range(i*2, n, i):
            div_sum[j] += i
    #for i in range(1, n):
     #   div_sum[i] = sum([j + i/j for j in range(2, int(math.sqrt(i)) + 1) if i % j == 0 and i != i/j])
      #  div_sum[i] = div_sum[i] + 1

    #print div_sum
    for j in range(n):
        if div_sum[j] < n and div_sum[div_sum[j]] == j and div_sum[j] != j:
            amicable_pairs_set[j] = j
            amicable_pairs_set[div_sum[j]] = div_sum[j]
    return sum(amicable_pairs_set)

Java代码1：

public class AmicableNumbers {

    public static void main(String[] args) {
        long strTime = System.currentTimeMillis();
        int sum_ami = 0;
        for (int j = 1; j < 1000000; j++) {
            int ad = sum_devisors(j);
            if (((sum_devisors(ad)) == j) && (j != ad)) {
                sum_ami += j;
            }
        }
        System.out.println(sum_ami);
        long endTime = System.currentTimeMillis();
        System.out.println("time is " + (endTime - strTime) + " ms");
    }

    public static int sum_devisors(int number) {
        if ((number == 1) || (number == 2)) {
            return 1;
        }
        int sum = 0;
        int k = (int) Math.sqrt(number);
        for (int i = 2; i < k; i++) {
            if (number % i == 0) {
                sum += i;
                sum += (number / i);
            }
        }
        if (k * k == number) {
            sum += k;
        }
        return (sum + 1);// every number divided by 1
    }
}

Java代码2：

import java.util.Scanner;

public class AmicableNumbers {

    /**
     * @author Pavan Koppolu
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        //scan the input
        System.out.println("Enter a number, to find out sum of amicable numbers: ");
        Scanner scan=new Scanner(System.in);
        int input=scan.nextInt();
        long before=System.currentTimeMillis();
        // getting the result
        long result=sumOfAllAmicableNumbersUptoGivenNumber(input);
        long after=System.currentTimeMillis();
        // prints the result on the console
        System.out.println("Sum of all amicable numbers below "+input+" : "+result+" Elasped Time : "+(after-before)+" ms");
    }
    /*
     * calculate the sum of the amicable numbers upto the given number
     */
    private static long sumOfAllAmicableNumbersUptoGivenNumber(int input)
    {
        long sum=0,factorsSum=0,sumOfFactors=0; 
        for(long j=2;j<input;j++)
        {
            factorsSum=getFactorsSum(j);
            if(j!=factorsSum)
            {
                sumOfFactors=getFactorsSum(factorsSum);
                if(j==sumOfFactors)
                    sum+=j;
            }   
            else
                continue;
        }       
        return sum;
    }
    /*
     * find out the sum of the factors
     */
    private static long getFactorsSum(long j)
    {
        long sum=1;
        for(int k=2;k<=Math.sqrt(j);k++)
        {
            if(j%k==0)
                sum+=k+j/k;
        }
        return sum;
    }
}

实际上，对于 1000000 的输入，上述所有三个返回的解决方案彼此不同

4

1 回答 1

6

关键是，有一对朋友小于100万，另一个大于100万，即

(947835,1125765), (998104,1043096)

Python代码不计算它们，

for j in range(n):
    if div_sum[j] < n and div_sum[div_sum[j]] == j and div_sum[j] != j:

但是 Java 代码会计算这些对中较小的成员。这解释了第二个 Java 代码的输出，因为

25275024 + 947835 + 998104 == 27220963

第一个 Java 代码的输出较小，因为它省略了友好对

(356408, 399592)

原因是

356408 = 596*598

但在代码中有

int k = (int) Math.sqrt(number);
for (int i = 2; i < k; i++) {

因此，对于所有可被非平方数整除的数字，除数和计算错误floor(sqrt(n))（请注意，第二个 Java 代码错误计算了所有平方的除数）。

于 2012-07-16T17:03:00.720 回答