论坛 › 欧拉计划（Project Euler） › 题目95：找出元素都不超过一百万的亲和链中最小的元素

欧拉计划 发表于 2016-8-11 23:24:24

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

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

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

愤怒的大头菇 发表于 2016-11-22 21:17:12

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)
list3.sort()
print(list3)
效率低得不行，结果：14316

jerryxjr1220 发表于 2017-1-5 17:06:33

本帖最后由 jerryxjr1220 于 2017-1-5 21:59 编辑

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

我的效率也好低，2分钟才能出结果。。。
# -*- coding: utf-8 -*-
"""
Created on Thu Jan5 21:21:52 2017

@author: Jerry Xu
"""

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

芒果加黄桃 发表于 2017-3-10 14:54:43

# encoding:utf-8
# 找出不超过100万的亲和链中的最小元素
from time import time
N = 1000000
l_sums, l_lens = * (2 * N), * (2 * N)
def getFacSum():
    for i in range(2, N // 2 + 1):
      for t in range(2 * i, N + 1, i):
            l_sums += 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 > N + 1:
                break
            if l_sums not in s_t:
                s_t.append(l_sums)
                t = l_sums
            else:
                s_t = s_t):]
                flag = True
                break
      if flag:
            l_lens] = 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
cost 16.423642 sec

fc1735 发表于 2020-6-4 15:10:14

bound = int(1e6)

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

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

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

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

永恒的蓝色梦想 发表于 2020-12-31 22:23:55

本帖最后由 永恒的蓝色梦想 于 2021-2-19 10:58 编辑

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;
    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 += i;
      }
    }


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

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

                        if (length > max_length) {
                            max_length = length;

                            for (min_of_longest = chain; index < chain.size(); index++) {
                              if (chain < min_of_longest) {
                                    min_of_longest = chain;
                              }
                            }
                        }
                  }

                  break;
                }
            }

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


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

guosl 发表于 2022-1-27 17:22:36

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

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, *nMinElements = new int;
#pragma omp parallel shared(nMaxLens,nMinElements)
{
#pragma omp for
    for (int i = 0; i < ps; ++i)
    {
      nMaxLens = 0;
      nMinElements = N;
    }
#pragma omp for schedule(guided,4)
    for (int i = 2; i <= N; ++i)
      a = 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;
      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)
          {
            nMaxLens = nc;
            nMinElements = *min_element(itr, v.end());
          }
          break;
      }
      }
    }
}
for (int i = 1; i < ps; ++i)
{
    if (nMaxLens > nMaxLens)
    {
      nMaxLens = nMaxLens;
      nMinElements = nMinElements;
    }
}
t = omp_get_wtime() - t;
cout << nMinElements << endl << t << endl;;
delete[] nMaxLens;
delete[] nMinElements;
return 0;
}

查看完整版本: 题目95：找出元素都不超过一百万的亲和链中最小的元素