Pythonの問題21の解決策があり、正しい答えが得られます。他の誰かの Java コードを試してみたところ、10000 と 100000 の値に対して同じ答えが得られましたが、1000000 を試してみると、返された 3 つのソリューションはすべて同じであるにもかかわらず、私のコードによって返されたソリューションは、Java コードによって返された他の 2 つのソリューションとは異なります。 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;
}
}
実際、上記の 3 つすべてによって返されるソリューションは、1000000 の入力に対して互いに異なります。