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

#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
耗时：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;
}

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

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