题目95：找出元素都不超过一百万的亲和链中最小的元素

欧拉计划

Amicable chains

The proper divisors of a number are all the divisors excluding the number itself. For example, the proper divisors of 28 are 1, 2, 4, 7, and 14. As the sum of these divisors is equal to 28, we call it a perfect number.

Interestingly the sum of the proper divisors of 220 is 284 and the sum of the proper divisors of 284 is 220, forming a chain of two numbers. For this reason, 220 and 284 are called an amicable pair.

Perhaps less well known are longer chains. For example, starting with 12496, we form a chain of five numbers:

12496 → 14288 → 15472 → 14536 → 14264 (→ 12496 → ...)

Since this chain returns to its starting point, it is called an amicable chain.

Find the smallest member of the longest amicable chain with no element exceeding one million.

题目：

一个数的真因子是指除了其本身以外的所有因子。例如，28 的真因子是 1,2,4,7 和 14。因为这些因子之和等于 28，我们称 28 为一个完美数。

有趣的是，220 的真因子之和是 284，而 284 的真因子之和是 220，形成了一个两个元素的链。因此 220 和 284 被称为一个亲和对。

可能更长的链就不那么为人所知了，例如，从 12496 开始，我们可以得到一个五个元素的链：

12496 → 14288 → 15472 → 14536 → 14264 (→ 12496 → ...)

因为这条链最后回到了开始的数，它被称为一条亲和链。

对于元素都不超过一百万的亲和链，找出最长的亲和链中最小的元素。

愤怒的大头菇

import math
def Hr(x):
    count =1
    for i in range(2,int(math.sqrt(x)+1)):
        if x % i == 0:
            if i!= x/i:
                count += i+x/i
            else:
                count += i
    return int(count)
def Prime(x):
    if x > 1:
        if x==2:
            return True
        if x%2==0:
            return False
        for i in range(3,int(math.sqrt(x)+1),2):
            if x%i==0:
                return False
        return True
    return False
i=4
temp = i
list1=[]
list2 = []
while True:
    if not Prime(i):
        list2=[]
        while temp != 1:
            temp = Hr(temp)
            if temp in list2:
                break
            if i not in list2:
                list2.append(i)
            if temp not in list2:
                list2.append(temp)
            if temp > 1000000:
                break
                
            if temp == i:
                break
        if temp == i and temp<1000000:
            list1.append(list2)
    i += 1
    temp = i
    if i > 1000000:
        break
tmp = 0
for each in list1:
    each.sort()
    if len(each) > tmp:
        tmp = len(each)
list3=[]
for each in list1:
    if len(each) == tmp:
        list3.append(each[0])
list3.sort()
print(list3[0])

效率低得不行，结果：14316

jerryxjr1220

愤怒的大头菇 发表于 2016-11-22 21:17
效率低得不行，结果：14316

我的效率也好低，2分钟才能出结果。。。

# -*- coding: utf-8 -*-
"""
Created on Thu Jan  5 21:21:52 2017

@author: Jerry Xu
"""

primes = [True]*1000001
primes[0], primes[1] = False, False
for i,prime in enumerate(primes):
        if prime:
                for j in range(i*i,1000001,i):
                        primes[j] = False
dic = {}
chain = {}
chains = {}
def ele(n):
        if primes[n]:
                dic[n] = [1]
        else:
                dic[n] = [1]
                for i in range(2,int(n**0.5+1)):
                        if n % i == 0 and i*i != n:
                                dic[n] += [i,n//i]
                        elif i*i == n:
                                dic[n] += [i]
        chain[n] = sum(dic[n])
def find(x):
        tmp = [x]
        y = chain[x]
        while True:
                if y > 1000000:
                        tmp = []
                        chains[y] = 0
                        break
                else:
                        if y in tmp:
                                index = tmp.index(y)
                                if len(tmp)-index > chains.get(y,0):
                                        chains[y] = len(tmp)-index
                                break
                        else:
                                tmp.append(y)
                                y = chain[y]
        return y,chains[y]
for i in range(1,1000001):
        ele(i)
maxlength = 0
for i in range(1,1000001):
        if find(i)[1] > maxlength:
                maxlength = find(i)[1]
                maxi = find(i)[0]
k = maxi
longest = []
for i in range(maxlength):
        k = chain[k]
        longest.append(k)
print (min(longest))

结果和你是一样的：
14316
[Finished in 123.9s]

芒果加黄桃

# encoding:utf-8
# 找出不超过100万的亲和链中的最小元素
from time import time
N = 1000000
l_sums, l_lens = [1] * (2 * N), [0] * (2 * N)
def getFacSum():
    for i in range(2, N // 2 + 1):
        for t in range(2 * i, N + 1, i):
            l_sums[t] += i
def euler095():
    getFacSum()
    max_len_nums = set()
    for i in range (1, N + 1):
        s_t , t, flag = list(), i, False
        s_t.append(t)
        while True:
            if l_sums[t] > N + 1:
                break
            if l_sums[t] not in s_t:
                s_t.append(l_sums[t])
                t = l_sums[t]
            else:
                s_t = s_t[s_t.index(l_sums[t]):]
                flag = True
                break
        if flag:
            l_lens[s_t[0]] = len(s_t)
            if len(s_t) > len(max_len_nums):
                max_len_nums = s_t.copy() 
    print(max_len_nums)
    print(min(max_len_nums))
if __name__ == '__main__':
    start = time() 
    euler095()
    print('cost %.6f sec' % (time() - start))

[14316, 19116, 31704, 47616, 83328, 177792, 295488, 629072, 589786, 294896, 358336, 418904, 366556, 274924, 275444, 243760, 376736, 381028, 285778, 152990, 122410, 97946, 48976, 45946, 22976, 22744, 19916, 17716]
14316
cost 16.423642 sec

fc1735

bound = int(1e6)

count = [0] * bound
for i in range(1, bound // 2):
  for j in range(2 * i, bound, i):
    count[j] += i

flag = [0] * bound
def find(n):
  if flag[n] == 0:
    s = set()
    p = n
    while p not in s:
      s.add(p)
      flag[p] = -1
      p = count[p]
      if p > bound:
        return -1
    l = list()
    while p in s:
      l.append(p)
      s.remove(p)
      p = count[p]
    for i in l:
      flag[i] = len(l)
  return flag[n] 

print(max(range(1, bound), key = find))

https://github.com/devinizz/project_euler/blob/master/page02/95.py

永恒的蓝色梦想

C++ 151ms

#include<iostream>
#include<vector>
#include<unordered_map>



int main() {
    using namespace std;
    ios::sync_with_stdio(false);

    constexpr static unsigned int UPPER_BOUND = 1000000;
    static unsigned int prime_divisor_sum[UPPER_BOUND + 1];
    unordered_map<unsigned int, unsigned int> indecies;
    vector<unsigned int> chain;
    unsigned int i, copy_i, temp, min_of_longest = 0, max_length = 0;
    unsigned int & index = copy_i, & length = temp;//别名


    for (i = 1; i <= UPPER_BOUND / 2; i++) {
        for (temp = i << 1; temp <= UPPER_BOUND; temp += i) {
            prime_divisor_sum[temp] += i;
        }
    }


    for (i = 1; i <= UPPER_BOUND; i++) {
        if (prime_divisor_sum[i]) {
            chain.push_back(i);
            indecies[i] = 1;
            copy_i = prime_divisor_sum[i];
            prime_divisor_sum[i] = 0;

            for (;;) {
                if (copy_i > UPPER_BOUND) {
                    break;
                }
                else if (prime_divisor_sum[copy_i]) {
                    chain.push_back(copy_i);
                    indecies[copy_i] = chain.size();
                    temp = prime_divisor_sum[copy_i];
                    prime_divisor_sum[copy_i] = 0;
                    copy_i = temp;
                }
                else {
                    if (index = indecies[copy_i]) {
                        length = chain.size() - index;//比真的长度少1

                        if (length > max_length) {
                            max_length = length;

                            for (min_of_longest = chain[index - 1]; index < chain.size(); index++) {
                                if (chain[index] < min_of_longest) {
                                    min_of_longest = chain[index];
                                }
                            }
                        }
                    }

                    break;
                }
            }

            indecies.clear();
            chain.clear();
        }
    }


    cout << min_of_longest << endl;
    return 0;
}

guosl

/*
答案：14316
耗时：2.58101秒（单核）
      0.287085秒（八核）
*/
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <omp.h>
using namespace std;

const int N = 1000000;
int a[N + 1];

int getAmi(int n)
{
  int r = 1;
  for (int i = 2; i <= (int)sqrt((double)n); ++i)
  {
    if (n%i == 0)
    {
      int m = n / i;
      if (m != i)
        r += m + i;
      else
        r += i;
    }
  }
  if (r <= N)
    return r;
  else
    return -1;
}

int main(void)
{
  double t = omp_get_wtime();
  int ps = omp_get_num_procs();
  int *nMaxLens = new int[ps], *nMinElements = new int[ps];
#pragma omp parallel shared(nMaxLens,nMinElements)
  {
#pragma omp for
    for (int i = 0; i < ps; ++i)
    {
      nMaxLens[i] = 0;
      nMinElements[i] = N;
    }
#pragma omp for schedule(guided,4)
    for (int i = 2; i <= N; ++i)
      a[i] = getAmi(i);
#pragma omp for schedule(dynamic)
    for (int i = 2; i <= N; ++i)
    {
      int pt = omp_get_thread_num();
      vector<int> v;
      int k = i;
      bool bFind = false;
      while (true)
      {
        v.push_back(k);
        k = a[k];
        if (k <= 1)
          break;
        auto itr = find(v.begin(), v.end(), k);
        if (itr != v.end())
        {
          int nc = int(v.end() - itr);
          if (nc > nMaxLens[pt])
          {
            nMaxLens[pt] = nc;
            nMinElements[pt] = *min_element(itr, v.end());
          }
          break;
        }
      }
    }
  }
  for (int i = 1; i < ps; ++i)
  {
    if (nMaxLens[i] > nMaxLens[0])
    {
      nMaxLens[0] = nMaxLens[i];
      nMinElements[0] = nMinElements[i];
    }
  }
  t = omp_get_wtime() - t;
  cout << nMinElements[0] << endl << t << endl;;
  delete[] nMaxLens;
  delete[] nMinElements;
  return 0;
}