题目21：计算10000以下所有相亲数之和

欧拉计划

Amicable numbers

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).

If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2,

4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.

题目：

d(n) 定义为 n 的所有真因子（小于 n 且能整除 n 的整数）之和。

如果 d(a) = b 并且 d(b) = a, 且 a ≠ b, 那么 a 和 b 就是一对相亲数（amicable pair），并且 a 和 b 都叫做亲和数（amicable number）。

例如 220 的真因子是 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 和 110; 因此 d(220) = 284. 284 的真因子是 1, 2, 4, 71 和 142; 所以 d(284) = 220.

计算 10000 以下所有亲和数之和。

Estein

结果为：31626
代码如下:

result = []
for n in range(1,10000):
    factor1 = []
    s = 0
    for i in range(1,n):
        if n % i == 0:
            factor1.append(i)
            s += i
    factor2 = []
    s2 = 0
    for j in range(1,s):
        if s % j == 0:
            factor2.append(j)
            s2 += j
    if (s2 == n) and (s2 != s):
        result.append(n)
final = sum(result)
print(final)
            

计算效率比较低，求后续优化

Plusenxue

def d(x):
    n = 0
    for i in range(1,x):
        if x%i == 0:
            n += i
    return n



result = 0



for x in range(2,10000):
    if d(x) == x:
        continue
    if d(d(x)) == x:
        result += x

print(result//2)

愤怒的大头菇

def TrueBec(x):
    list1=[]
    for i in range(1,x):
        if x % i == 0:
            list1.append(i)
    return sum(list1)


def Judg(i):
    temp = TrueBec(i)
    if i == TrueBec(temp) and i != temp:
        return True


list1 = []


for i in range(10000):
    if Judg(i):
        list1.append(i)


print(sum(list1))

jerryxjr1220

31626
[Finished in 0.2s]

def y(n):
        lst = [1]
        for i in range(2,int(n**0.5+1)):
                if n%i == 0:
                        lst.append(i)
                        lst.append(int(n//i))
        return lst

master = [0]*100000
for j in range(1,10001):
        if j == 1:
                master[j] = 1
        elif j == 2:
                master[j] = 1
        else:
                master[j] = sum(y(j))
summ = 0
for k in range(1,10000):
        if k == master[master[k]] and master[k] != k:
                print master[k], k
                summ += k
print summ

376103327

def getSum(num):
    listnum = []
    for i in range(1, int(num/2) + 1):
        if num % i == 0:
            listnum.append(i)
    return sum(listnum)

list1 = []
for i in range(1, 10000):
    if getSum(getSum(i)) == i:
        list1.append(i)
print list1
print sum(list1)

40284

芒果加黄桃

# encoding:utf-8
# 10000以内的亲和数之和
from time import time
def getFactorsSum(N):
    l_result = [1]
    for t in range(2,int(N**0.5)+1):
        if N%t == 0:
            l_result.append(t)
            l_result.append(N//t);
    return sum(l_result)
def euler020():
    l_r = []
    dic_sum = {}
    for N in range(1,10001):
        dic_sum[N] = getFactorsSum(N)
    for i in range(1,10001):
        if i == dic_sum.get(dic_sum[i]) and i != dic_sum[i]:
            l_r.append(i)
            l_r.append(dic_sum[i])
    s = set(l_r) 
    return s 
if __name__ == '__main__':
    start = time()
    print(sum(euler020()))
    print('cost %.6f sec' % (time() - start))

31626
cost 0.132000 sec

渡风

此代码使用matlab编程
Problem21所用时间为8.6064秒
Problem21的答案为31626

%题目21：计算10000以下所有相亲数之和
%标记法
function Output=Problem21(Input)
 tic
if nargin==0
    Input=10000;
end
Sum=0;
One=2:Input;
 Flag=zeros(1,Input-1);%用标记法
 for ii=1:Input-1
     if Flag(ii)==0
         Other=sum(Factor_Num(One(ii)));
         if sum(Factor_Num(Other))==One(ii)&&Other~=One(ii);
             Sum=Sum+One(ii)+Other;
         end
         Flag(ii)=1;
         if isempty(find(One==Other, 1))==0
             Flag(One==Other)=1;
         end
     end
 end
Output=Sum;
disp('此代码使用matlab编程')
disp(['Problem21所用时间为',num2str(toc),'秒'])
disp(['Problem21的答案为',num2str(Output)])
end
%% 子程序
%输入一个数得到一个数的真因子的序列（乱序）。
function Output=Factor_Num(Input)
if nargin==0
    Input=10000;
end
    Start=2;
    Stop=Input-1;
    Rank=[];
    while (Stop>Start)
        for ii=Start:Stop
            if mod(Input,ii)==0
                if Input==ii^2
                    Temp=[Rank,ii];
                else
                    Temp=[ii,Rank,Input/ii];
                end
                Rank=Temp;
                Start=ii+1;
                Stop=Input/ii-1;
                break
            else
                Start=Start+1;
                Stop=Stop-1;
            end
        end
    end
    Output=[1,Rank];
end

marmot

def d(n):
    num = 0
    # 真因子不算自己
    for i in range(1,n):
        if n % i == 0 :
            num += i
    return num

sum_num = 0
print('亲和数为：')
for i in range(1,10000):
    # i等于自己倒数的倒数，还不能等于自己才符合
    if i == d(d(i)) and i != d(i):
        sum_num +=  i
        print(i, end="/")
print('')
print('答案为： ' +str(sum_num))

99592938

def d(x):
    l=[1]
    for i in range(2,int(x**0.5)+1):
        if not x%i:
            if x==i**2:
                l.append(i)
            else:l.extend((i,x//i))
    return sum(l)

def Ami(x):
    if d(x)<10000 and d(x)!=x and d(d(x))==x:return 1
    else:return 0

list2=[]
for i in range(10000):
    if Ami(i):
        list2.append(i)
print(sum(list2),'\n',list2)

结果：
>>>
31626
[220, 284, 1184, 1210, 2620, 2924, 5020, 5564, 6232, 6368]

由我们主宰

#include<stdio.h>
#include<time.h>
int CalculateFactorSum(int x)
{
        int i,sum=0;
        for(i=1;i<x;i++)
        {
                if(0==x%i)
                {
                        sum=sum+i;
                }        
        }
        return sum;
}
int Judge(int x)
{
        int y1,y2;
        y1=CalculateFactorSum(x);
        y2=CalculateFactorSum(y1);
        if(x==y2&&x!=y1)
        {
                printf("%d\t",x);
                return 1;
        }
        else
        {
                return 0;
        }
}
int main()
{
                int i,sum=0;
                clock_t start,end;
                start=clock();
                for(i=1;i<10000;i++)
                {
                        if(Judge(i))
                        {
                                        sum=sum+i;
                        }
                }
                end=clock();
                printf("\n%d\n",sum);
                printf("本次计算用时%f秒\n",(double)(end-start)/CLK_TCK);
}

najin

31626
Time is 6 ms

zzzgod

#include <iostream>
#include <cmath>
using namespace std;
int sumyz(int num)
{
        int sum=0;
        double a;
        for(int i=1;i<=(int)sqrt(num);++i)
        {
                if(num%i==0)
                {
                        sum+=num/i+i;
                }
        }
        a=(double)num;
        if(a==(int)sqrt(num)*(int)sqrt(num))
        {
                sum-=sqrt(num);
        }
        sum-=num;
        return sum;
}
int main()
{
        bool isqin[10001]={0};
        int num,sum=0;
        for(int i=1;i<=10000;++i)
        {
                if(isqin[i]==1)
                {
                        continue;
                }
                if(i==sumyz(sumyz(i))&&i!=sumyz(i))
                {
                       
                        isqin[i]=1;
                        isqin[sumyz(i)]=1;
                }
        }
        for(int i=1;i<=10000;++i)
        {
                if(isqin[i]==1)
                {
                        sum+=i;
                }
        }
        cout<<sum;
}

@小狮子

[1, 2, 4, 5, 5000, 8, 10, 16, 400, 20, 25, 40, 50, 2500, 200, 2000, 80, 1250, 1000, 625, 500, 250, 125]
我的答案是14111
难道我理解错题目了？？

k往事如烟k

def d(n):
    sum = 0
    for i in range(1, n // 2 + 1):
        if n % i == 0:
            sum += i
    return sum

sum = 0
for i in range(1, 10000):
    if i == d(d(i)) and d(i) > i:
        sum += i + d(i)

print(sum)

31626

cwhsmile

答案和楼上的几位一样，看了人家的代码才明白自己的思路问题出来哪里。

import time
import math

def test1():
    dict1 = {}
    result = 0
    for m in range(1,10001):
        li = []
        num = 0
        for n in range(1,int(math.sqrt(m))+1):
            if m%n == 0:
                li.append(n)
        if len(li) == 1:
            dict1[m] = li[0]
            continue
        for o in li[1:-1]:
            num = num + o + m//o
        last = li[-1]
        if last**2 == m:
            num += last
        else:
            num = num + last + m//last
        dict1[m] = num+1
    
    print(f'220因子是{dict1[220]}，284的因子是{dict1[284]}')
    for i in dict1:
        d_i = dict1[i]
        if d_i == 0:
            continue
        for j in dict1:
            if d_i ==j:
                d_j = dict1[j]
                if d_j == 0:
                    continue
                if d_j == i:
                    if i != j:
                        result = result + i + j
                        dict1[i] = 0
                        dict1[j] = 0


    return result
li = []
start = time.perf_counter()
print(test1())
end = time.perf_counter()
print(end-start)

成为极客

def d(x):
    n = 0
    for i in range(1,x):
        if x%i == 0:
            n += i
    return n

count = 0
for x in range(2,10000):
    if d(x) == x:
        continue
    if d(d(x)) == x:
        count += x
print(count)

31626

王小召

Result: 31626
用时:3.5559223331028966

import time

def get_sum(num):
    tmp_list = []
    result_list = []
    for num in range(1, num+1):
        tmp_list.append(sum([i for i in range(1, num) if not num % i]))
    for i, j in enumerate(tmp_list):
        if tmp_list[i]-1 <= 10000 and tmp_list[tmp_list[i]-1] == i+1 and i+1 != tmp_list[i]:
            result_list.extend([i+1, tmp_list[i]])
    return sum(set(result_list))

start = time.clock()
print("Result: {} \n用时:{}".format(get_sum(10000), time.clock()-start))

永恒的蓝色梦想

31626

#include<iostream>
unsigned i, j, sum = 0, d[30001];



int main() {
    using namespace std;
    ios::sync_with_stdio(false);


    for (i = 1; i <= 15000; i++) {
        for (j = i * 2; j <= 30000; j += i) {
            d[j] += i;
        }
    }

    for (i = 1; i < 10000; i++) {
        j = d[i];

        if (j != i && d[j] == i) {
            sum += i;
        }
    }


    cout << sum << endl;
    return 0;
}

leon0149

31626
0.031 s

#include <stdio.h>
#include <math.h>
#include <time.h>

int main(void)
{
    clock_t start, finish;
    double duration;
    start = clock();

    int sum = 1;
    int sum2 = 1;
    int sum3 = 0;
    for (int i =  4; i < 10000; ++i) {
        for (int j = 2; j <= sqrt(i); ++j) {
            if (i % j == 0){
                if (i / j == j)
                    sum += j;
                else
                    sum += j + i / j;
            }
        }
        for (int j = 2; j <= sqrt(sum); ++j) {
            if (sum % j == 0){
                if (sum / j == j)
                    sum2 += j;
                else
                    sum2 += j + sum / j;
            }
        }
        if (i == sum2){
            if (sum != sum2)
                sum3 += sum2 + i;
        }
        sum = 1;
        sum2 = 1;
    }

    printf("%d\n", sum3 / 2);

    finish = clock();

    duration = (double )(finish - start)/CLOCKS_PER_SEC;

    printf("%.3f s\n", duration);
    return 0;
}