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

有马_冬巳

1. '''计算小于10000的所有亲和数之和'''
   
2. 
   
3. def amicable(num):
   
4.     sum = 0
   
5.     Amicable = {}
   
6.     AMICABLE = []
   
7.     AMI = {}
   
8. 
   
9.     for number in range(1,num):
   
10.         factsum = 0
    
11. 
    
12.         for factors in range(1,int(number/2)+1):
    
13.             if number % factors == 0:
    
14.                 factsum += factors
    
15.         Amicable[number] = factsum
    
16. 
    
17.     for i in range(1,len(Amicable)):
    
18.         for j in range(1,len(Amicable)):
    
19.             if Amicable[i] == j and Amicable[j] == i and i != j:
    
20.                 AMICABLE.append(i)
    
21.                 AMICABLE.append(j)
    
22. 
    
23.     AMICABLE = list(set(AMICABLE))
    
24.     print("在%d以下的亲和数为：" %num)
    
25.     print(AMICABLE)
    
26.     for numbers in AMICABLE:
    
27.         AMI[numbers] = Amicable[numbers]
    
28.         sum += numbers
    
29. 
    
30.     print("它们分别的因数和为：")
    
31.     print(AMI)
    
32.     print("它们的因数总和为：%d" %sum)
    
33. 
    
34. start_amicable = time.time()
    
35. amicable(10000)
    
36. time_amicable = time.time() - start_amicable
    
37. 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

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

1. #include <stdio.h>
   
2. #include <time.h>
   
3. 
   
4. main()
   
5. {
   
6.         int i, j, k, sum = 0, temp, x, y, z, a;
   
7.         int begin, end;
   
8.        
   
9.         begin = time(NULL);
   
10.        
    
11.         for (i = 10; i < 10000; i++)
    
12.         {
    
13.                 if (i == z) //当找到一个亲和数，它的相亲数直接跳过循环
    
14.                 {
    
15.                         sum += z;
    
16.                         goto Label;
    
17.                 }
    
18.                 k = i / 2;
    
19.                 temp = 0;
    
20.                 y = 0;
    
21.                 for (j = 2; j <= k; j++)//找真因子
    
22.                 {
    
23.                         if (i % j == 0)
    
24.                         {
    
25.                                 temp += j;
    
26.                         }
    
27.                 }
    
28.                 temp++;
    
29.                 z = temp;
    
30.                 x = temp / 2;
    
31.                 for (j = 2; j <= x; j++)//找真因子
    
32.                 {
    
33.                         if (temp % j == 0)
    
34.                         {
    
35.                                 y += j;
    
36.                         }
    
37.                 }
    
38.                 y++;
    
39.                 if (y == i && y != z)
    
40.                 {
    
41.                         sum += i;
    
42. 
    
43.                         a = z;
    
44.                 }
    
45.         Label:continue;
    
46.         }
    
47.         end = time(NULL);
    
48.         printf("%d\n", sum);
    
49.         printf("time = %d", end - begin);
    
50. }

复制代码

31626
time = 0

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

ft215378

#计算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

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

1. /*
   
2. 答案：31626
   
3. 耗时：0.0072575秒
   
4. */
   
5. #include <iostream>
   
6. using namespace std;
   
7. 
   
8. const int N = 10000;
   
9. char a[N + 4];
   
10. 
    
11. int getFactorsSum(int n)//计算n的各因数之和
    
12. {
    
13.   int d = (int)sqrt((double)n);
    
14.   int s = 1;
    
15.   for (int i = 2; i <= d; ++i)
    
16.   {
    
17.     if (n % i == 0)
    
18.     {
    
19.       int m = n / i;
    
20.       if (m == i)
    
21.         s += i;
    
22.       else
    
23.         s += i + m;
    
24.     }
    
25.   }
    
26.   return s;
    
27. }
    
28. 
    
29. int main(void)
    
30. {
    
31.   int nS = 0;
    
32.   for (int i = 2; i <= N; ++i)
    
33.   {
    
34.     if (a[i] == 0)
    
35.     {
    
36.       int k = getFactorsSum(i);//计算i的各因数之和
    
37.       if (k != i)//各因数之和不能等于自身
    
38.       {
    
39.         int k1 = getFactorsSum(k);//计算k的各位因数之和
    
40.         if (k1 == i) //i和k是互为亲和数
    
41.         {
    
42.           a[i] = 1;
    
43.           nS += i;
    
44.           if (k <= N)
    
45.             a[k] = 1;
    
46.         }
    
47.       }
    
48.     }
    
49.     else
    
50.       nS += i;
    
51.   }
    
52.   cout << nS << endl;
    
53.   return 0;
    
54. }
    

复制代码

B1tetheDust

1. import time as t
   
2. 
   
3. start = t.perf_counter()
   
4. 
   
5. 
   
6. def seeking_factor(a_num):
   
7.     factors = []
   
8.     if a_num >= 1:
   
9.         factors.append(1)
   
10.     else:
    
11.         return factors
    
12.     divisor = 2
    
13.     upper_limit = a_num
    
14.     while divisor < upper_limit:
    
15.         if not a_num % divisor:
    
16.             factors.append(divisor)
    
17.             upper_limit = int(a_num / divisor)
    
18.             factors.append(upper_limit)
    
19.         divisor += 1
    
20.     # factors.sort()
    
21. 
    
22.     return factors
    
23. 
    
24. 
    
25. affinity_nums = []
    
26. num_bool = []
    
27. for i in range(10000):
    
28.     num_bool.append(True)
    
29. 
    
30. for n in range(10000):
    
31.     if num_bool[n]:
    
32.         d_n = sum(seeking_factor(n))
    
33.         try:
    
34.             num_bool[d_n]
    
35.             a = sum(seeking_factor(d_n))
    
36.             if n == a and n != d_n:
    
37.                 affinity_nums.append(n)
    
38.                 affinity_nums.append(d_n)
    
39.                 num_bool[n] = False
    
40.                 num_bool[d_n] = False
    
41.             else:
    
42.                 num_bool[n] = False
    
43.         except IndexError:
    
44.             num_bool[n] = False
    
45. 
    
46. print(affinity_nums)
    
47. print(sum(affinity_nums))
    
48. 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

python
31626
时间：0.02099919319152832s

1. import time
   
2. tt=time.time()
   
3. n=10000
   
4. data=[1]*n
   
5. for i in range(2,int(n**0.5+1)):
   
6.     for j in range(i,n):
   
7.         if i*j>n:
   
8.             break
   
9.         elif i==j:
   
10.             data[i*j-1]=data[i*j-1]+i
    
11.         else:
    
12.             data[i*j-1]=data[i*j-1]+i+j
    
13. he=0
    
14. for i in range(1,n+1):
    
15.     if data[i-1]<=n and not data[i-1]==i:
    
16.         if data[data[i-1]-1]==i:
    
17.             he=he+i
    
18.             print(i)
    
19. print(he)
    
20. print("时间：{}s".format(time.time()-tt))

复制代码