论坛 › 欧拉计划（Project Euler） › 题目21：计算10000以下所有相亲数之和

欧拉计划 发表于 2015-4-23 16:16:53

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

本帖最后由 欧拉计划 于 2015-4-23 16:19 编辑

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 发表于 2016-8-21 21:04:01

结果为：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 发表于 2016-8-27 17:29:36

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)

愤怒的大头菇 发表于 2016-8-28 22:09:55

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 发表于 2016-9-19 08:30:38

本帖最后由 jerryxjr1220 于 2016-10-11 23:07 编辑

31626


def y(n):
        lst =
        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 = *100000
for j in range(1,10001):
        if j == 1:
                master = 1
        elif j == 2:
                master = 1
        else:
                master = sum(y(j))
summ = 0
for k in range(1,10000):
        if k == master] and master != k:
                print master, k
                summ += k
print summ

376103327 发表于 2016-10-26 17:15:11

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

芒果加黄桃 发表于 2017-1-11 15:08:39

# encoding:utf-8
# 10000以内的亲和数之和
from time import time
def getFactorsSum(N):
    l_result =
    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 = getFactorsSum(N)
    for i in range(1,10001):
      if i == dic_sum.get(dic_sum) and i != dic_sum:
            l_r.append(i)
            l_r.append(dic_sum)
    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

渡风 发表于 2017-1-18 20:11:34

此代码使用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=;
                else
                  Temp=;
                end
                Rank=Temp;
                Start=ii+1;
                Stop=Input/ii-1;
                break
            else
                Start=Start+1;
                Stop=Stop-1;
            end
      end
    end
    Output=;
end

marmot 发表于 2017-3-8 23:44:42

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 发表于 2017-3-15 11:57:08

def d(x):
    l=
    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

由我们主宰 发表于 2018-3-16 21:16:44

#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 发表于 2018-4-7 23:26:59

31626
Time is 6 ms

zzzgod 发表于 2018-6-30 16:01:32

#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={0};
        int num,sum=0;
        for(int i=1;i<=10000;++i)
        {
                if(isqin==1)
                {
                        continue;
                }
                if(i==sumyz(sumyz(i))&&i!=sumyz(i))
                {
                       
                        isqin=1;
                        isqin=1;
                }
        }
        for(int i=1;i<=10000;++i)
        {
                if(isqin==1)
                {
                        sum+=i;
                }
        }
        cout<<sum;
}

@小狮子 发表于 2018-12-27 13:36:13

我的答案是14111
难道我理解错题目了？？

k往事如烟k 发表于 2019-3-25 14:17:21

本帖最后由 k往事如烟k 于 2019-3-25 14:39 编辑


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 发表于 2019-4-26 23:44:37

答案和楼上的几位一样，看了人家的代码才明白自己的思路问题出来哪里。
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 = li
            continue
      for o in li:
            num = num + o + m//o
      last = li[-1]
      if last**2 == m:
            num += last
      else:
            num = num + last + m//last
      dict1 = num+1
   
    print(f'220因子是{dict1}，284的因子是{dict1}')
    for i in dict1:
      d_i = dict1
      if d_i == 0:
            continue
      for j in dict1:
            if d_i ==j:
                d_j = dict1
                if d_j == 0:
                  continue
                if d_j == i:
                  if i != j:
                        result = result + i + j
                        dict1 = 0
                        dict1 = 0


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

成为极客 发表于 2019-5-30 11:53:15

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

王小召 发表于 2019-6-5 15:20:37

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())
    for i, j in enumerate(tmp_list):
      if tmp_list-1 <= 10000 and tmp_list-1] == i+1 and i+1 != tmp_list:
            result_list.extend(])
    return sum(set(result_list))

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

永恒的蓝色梦想 发表于 2019-8-6 12:21:03

本帖最后由 永恒的蓝色梦想 于 2021-2-8 16:26 编辑

31626#include<iostream>
unsigned i, j, sum = 0, d;



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 += i;
      }
    }

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

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


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

leon0149 发表于 2020-5-13 15:35:34

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;
}

查看完整版本: 题目21：计算10000以下所有相亲数之和