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

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

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

本帖最后由欧拉计划于 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
[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 · 发表于 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 = [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

渡风 · 发表于 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=[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 · 发表于 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=[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]

由我们主宰 · 发表于 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[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;
}

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

[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 · 发表于 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[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)

复制代码

成为极客 · 发表于 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([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))

复制代码

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

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

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 · 发表于 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;
}

复制代码

账号		自动登录	找回密码
密码			立即注册