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

有马_冬巳 · 发表于 2020-10-17 11:29:15

'''计算小于10000的所有亲和数之和'''
def amicable(num):
sum = 0
Amicable = {}
AMICABLE = []
AMI = {}
for number in range(1,num):
factsum = 0
for factors in range(1,int(number/2)+1):
if number % factors == 0:
factsum += factors
Amicable[number] = factsum
for i in range(1,len(Amicable)):
for j in range(1,len(Amicable)):
if Amicable[i] == j and Amicable[j] == i and i != j:
AMICABLE.append(i)
AMICABLE.append(j)
AMICABLE = list(set(AMICABLE))
print("在%d以下的亲和数为：" %num)
print(AMICABLE)
for numbers in AMICABLE:
AMI[numbers] = Amicable[numbers]
sum += numbers
print("它们分别的因数和为：")
print(AMI)
print("它们的因数总和为：%d" %sum)
start_amicable = time.time()
amicable(10000)
time_amicable = time.time() - start_amicable
print("%f秒" %time_amicable)

复制代码

在10000以下的亲和数为：
[1184, 6368, 5564, 5020, 2924, 284, 6232, 1210, 220, 2620]
它们分别的因数和为：
{1184: 1210, 6368: 6232, 5564: 5020, 5020: 5564, 2924: 2620, 284: 220, 6232: 6368, 1210: 1184, 220: 284, 2620: 2924}
它们的因数总和为：31626
7.503518秒

gonorth · 发表于 2020-11-16 11:42:10

def d(n):
div = []
i = 1
for i in range(1, n // 2 + 1):
      if n % i == 0:
         div.append(i)
#print (div)
sum = 0
for each in div:
      sum  += each
#print(sum)
return sum
def is_amicable(n1, n2):
if (d(n1) == n2) and (d(n2) == n1) and (n1 != n2):
      return True
return False

def calc(n):
am = []
while n :
      a = d(n)
      if is_amicable(a, n) and a != n:
         am.append(a)
         am.append(n)
      n = n - 1
am = set(am)
print (am)
sum = 0
for each in am:
      sum += each
print (sum)

a1351468657 · 发表于 2021-3-9 15:46:14

#include <stdio.h>
#include <time.h>
main()
{
int i, j, k, sum = 0, temp, x, y, z, a;
int begin, end;
begin = time(NULL);
for (i = 10; i < 10000; i++)
{
if (i == z) //当找到一个亲和数，它的相亲数直接跳过循环
{
sum += z;
goto Label;
}
k = i / 2;
temp = 0;
y = 0;
for (j = 2; j <= k; j++)//找真因子
{
if (i % j == 0)
{
temp += j;
}
}
temp++;
z = temp;
x = temp / 2;
for (j = 2; j <= x; j++)//找真因子
{
if (temp % j == 0)
{
y += j;
}
}
y++;
if (y == i && y != z)
{
sum += i;
a = z;
}
Label:continue;
}
end = time(NULL);
printf("%d\n", sum);
printf("time = %d", end - begin);
}

复制代码

31626
time = 0

自己进行了小小的优化，应该还有很多提升空间，望大佬指教！

ft215378 · 发表于 2021-10-15 12:15:49

#计算10000以下所有相亲数之和
def amicable_number(n):
ami = []
sum = 0
for i in range(1, n):
      if n % i == 0:
         ami.append(i)
for each in ami:
      sum += each
return sum

result = 0
for num in range(1, 10001):
a = amicable_number(num)
if amicable_number(a) == num and a != num:
      result += num

print(result)

guosl · 发表于 2022-1-2 20:13:57

本帖最后由 guosl 于 2022-1-2 20:26 编辑

此题可以打表记录亲和数，用空间换时间。

/*
答案：31626
耗时：0.0072575秒
*/
#include <iostream>
using namespace std;
const int N = 10000;
char a[N + 4];
int getFactorsSum(int n)//计算n的各因数之和
{
int d = (int)sqrt((double)n);
int s = 1;
for (int i = 2; i <= d; ++i)
{
if (n % i == 0)
{
int m = n / i;
if (m == i)
s += i;
else
s += i + m;
}
}
return s;
}
int main(void)
{
int nS = 0;
for (int i = 2; i <= N; ++i)
{
if (a[i] == 0)
{
int k = getFactorsSum(i);//计算i的各因数之和
if (k != i)//各因数之和不能等于自身
{
int k1 = getFactorsSum(k);//计算k的各位因数之和
if (k1 == i) //i和k是互为亲和数
{
a[i] = 1;
nS += i;
if (k <= N)
a[k] = 1;
}
}
}
else
nS += i;
}
cout << nS << endl;
return 0;
}

复制代码

B1tetheDust · 发表于 2022-7-11 11:15:12

import time as t
start = t.perf_counter()
def seeking_factor(a_num):
factors = []
if a_num >= 1:
factors.append(1)
else:
return factors
divisor = 2
upper_limit = a_num
while divisor < upper_limit:
if not a_num % divisor:
factors.append(divisor)
upper_limit = int(a_num / divisor)
factors.append(upper_limit)
divisor += 1
# factors.sort()
return factors
affinity_nums = []
num_bool = []
for i in range(10000):
num_bool.append(True)
for n in range(10000):
if num_bool[n]:
d_n = sum(seeking_factor(n))
try:
num_bool[d_n]
a = sum(seeking_factor(d_n))
if n == a and n != d_n:
affinity_nums.append(n)
affinity_nums.append(d_n)
num_bool[n] = False
num_bool[d_n] = False
else:
num_bool[n] = False
except IndexError:
num_bool[n] = False
print(affinity_nums)
print(sum(affinity_nums))
print("It costs %f s" % (t.perf_counter() - start))

复制代码

结果：
[220, 284, 1184, 1210, 2620, 2924, 5020, 5564, 6232, 6368]
31626
It costs 0.913826 s

TLM · 发表于 2022-12-20 19:26:58

python
31626
时间：0.02099919319152832s

import time
tt=time.time()
n=10000
data=[1]*n
for i in range(2,int(n**0.5+1)):
for j in range(i,n):
if i*j>n:
break
elif i==j:
data[i*j-1]=data[i*j-1]+i
else:
data[i*j-1]=data[i*j-1]+i+j
he=0
for i in range(1,n+1):
if data[i-1]<=n and not data[i-1]==i:
if data[data[i-1]-1]==i:
he=he+i
print(i)
print(he)
print("时间：{}s".format(time.time()-tt))

复制代码

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

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

浏览过的版块