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

有马_冬巳

'''计算小于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

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

#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

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

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

/*
答案：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

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

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))