题目88：考察不同大小集合的最小积和数

欧拉计划

Product-sum numbers

A natural number, N, that can be written as the sum and product of a given set of at least two natural numbers,   is called a product-sum number:

For example, 6 = 1 + 2 + 3 = 1 × 2 × 3.

For a given set of size, k, we shall call the smallest N with this property a minimal product-sum number. The minimal product-sum numbers for sets of size, k = 2, 3, 4, 5, and 6 are as follows.

Hence for 2≤k≤6, the sum of all the minimal product-sum numbers is 4+6+8+12 = 30; note that 8 is only counted once in the sum.

In fact, as the complete set of minimal product-sum numbers for 2≤k≤12 is {4, 6, 8, 12, 15, 16}, the sum is 61.

What is the sum of all the minimal product-sum numbers for 2≤k≤12000?

题目：

一个自然数N如果能写成一个两个元素以上的集合， ，中元素的积与和的话，该数字被称为积和数：

例如：6 = 1 + 2 + 3 = 1 × 2 × 3.

对于一个大小为 k 的集合，我们将最小的具有该性质的数字 N 成为一个最小积和数。k = 2, 3, 4, 5, 6 的集合的最小积和数如下：

因此对于 2≤k≤6, 所有最小积和数的总和为 4+6+8+12 = 30；注意 8 在求和时只计算一次。

事实上对于 2≤k≤12，所有最小积和数的集合是 {4, 6, 8, 12, 15, 16}，其和为 61。

对于 2≤k≤12000，所有最小积和数的和是多少？

jerryxjr1220

这题的思路是运用分解质因数，先把一个数分解成所有质因数。然后用1来补足不足的位数，如果补完后的和与原来相等，则找到积合数。
sum of minimal product-sum numbers: 7587457
max. number is 12200
[Finished in 0.8s]

1. import math
   
2. 
   
3. def factorize(n):
   
4.         f = []
   
5.         d = 2
   
6.         bound = math.sqrt(n)
   
7.         while d <= bound and n > 1:
   
8.                 if n % d == 0:
   
9.                         f.append(d)
   
10.                         n = n / d
    
11.                 else:
    
12.                         d = d + 1
    
13.         if n > 1:
    
14.                 f.append(n)
    
15.         return f
    
16. 
    
17. def factorizations(n):
    
18.         f = factorize(n)
    
19.         sol = set()
    
20.         sol.add(tuple())
    
21.         for p in f:
    
22.                 prev = sol
    
23.                 sol = set()
    
24.                 for pf in prev:
    
25.                         sol.add(tuple(sorted(pf + (p, ))))
    
26.                         t = list(pf)
    
27.                         for i in range(len(t)):
    
28.                                 t[i] *= p
    
29.                                 sol.add(tuple(sorted(t)))
    
30.                                 t[i] /= p
    
31.         return sol
    
32. 
    
33. kmax = 12000
    
34. mpsn = [ None ] * (kmax + 1)
    
35. rem = kmax - 1
    
36. 
    
37. n = 2
    
38. while rem > 0:
    
39.         for nf in factorizations(n):
    
40.                 no = n - sum(nf) # number of ones
    
41.                 k = no + len(nf)
    
42.                 if k < 2 or k > kmax:
    
43.                         continue
    
44.                 elif mpsn[k] is None:
    
45.                         mpsn[k] = n
    
46.                         rem -= 1
    
47.                
    
48.         n += 1
    
49.        
    
50. mpsns = set(mpsn[2:])
    
51. print 'sum of minimal product-sum numbers:', sum(mpsns)
    
52. print 'max. number is', n - 1

复制代码

fc1735

1. mem = []
   
2. used = set()
   
3. k = set(range(2, 12001))
   
4. for n in range(9999999999999999):
   
5.   mem.append(set())
   
6.   if len(k) == 0:
   
7.     break
   
8.   for p in range(2, 999999999999999999999):
   
9.     if p * p > n:
   
10.       break
    
11.     if n % p != 0:
    
12.       continue
    
13.     d = n // p
    
14.     for i in mem[d]:
    
15.       mem[n].add(i + n - p - d + 1)
    
16.   mem[n].add(1)
    
17.   for i in mem[n]:
    
18.     if i in k:
    
19.       k.remove(i)
    
20.       used.add(n)
    
21. 
    
22. print(sum(used))

复制代码

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

guosl

1. /*
   
2. 答案：7587456
   
3. 耗时：0.671572秒
   
4. */
   
5. #include <iostream>
   
6. #include <algorithm>
   
7. #include <vector>
   
8. #include <cmath>
   
9. #include <cstring>
   
10. using namespace std;
    
11. 
    
12. const int N = 12000;//欲求的范围
    
13. const int M = 24000;//计算的范围
    
14. 
    
15. int k[N + 1];//记录要求的结果
    
16. int fp[M];//fp[i]记录i的最小素因数
    
17. int pc[M];//记录i的素因数个数
    
18. 
    
19. /*
    
20. 对x进行分解为nc个因数的乘积
    
21. int nc 分解的因数个数
    
22. int x 要被分解的数
    
23. int nS 前面已经分解的因数和
    
24. vector<int> &v 记录整个分解的因数之和
    
25. */
    
26. void dfs(int nc, int x, int nS, vector<int> &v)//递归计算分解
    
27. {
    
28.   if (nc == 1)//分解结束
    
29.   {
    
30.     v.push_back(nS + x);
    
31.     return;
    
32.   }
    
33.   if (fp[x] == x)//x是素数无法分解
    
34.     return;
    
35.   for (int i = fp[x]; i <= (int)sqrt((double)x); ++i)//枚举x的可能因数
    
36.   {
    
37.     if (x%i == 0)
    
38.       dfs(nc - 1, x / i, nS + i, v);//继续下去
    
39.   }
    
40. }
    
41. 
    
42. int main(void)
    
43. {
    
44.   memset(k, -1, sizeof(k));//将k都预置为-1
    
45.   //应用筛法求每个数的最小素数数
    
46.   for (int i = 1; i < M; ++i)
    
47.     fp[i] = i;
    
48.   for (int i = 2; i <= (int)sqrt((double)M); ++i)
    
49.   {
    
50.     if (fp[i] < i)
    
51.       continue;
    
52.     for (int j = i*i; j < M; j += i)
    
53.       fp[j] = min(fp[j], i);
    
54.   }
    
55.   //计算每个数的素因数个数
    
56.   for (int i = 2; i < M; ++i)
    
57.   {
    
58.     int x = i;
    
59.     while (x > 1)
    
60.     {
    
61.       int y = fp[x];
    
62.       x /= y;
    
63.       ++pc[i];
    
64.     }
    
65.   }
    
66.   //计算k
    
67.   for (int i = 4; i < M; ++i)
    
68.   {
    
69.     if (fp[i] == i)//素数肯定不是和积数
    
70.       continue;
    
71.     for (int j = 2; j <= pc[i]; ++j)
    
72.     {
    
73.       vector<int> v;
    
74.       dfs(j, i, 0, v);//对i进行长度为j的因数分解
    
75.       for (auto itr = v.begin(); itr != v.end(); ++itr)//对不同的分解计算k
    
76.       {
    
77.         int u = i - *itr;//计算积与和的差，补上上这些1就成了和积数
    
78.         if (u >= 0 && u <= N)
    
79.         {
    
80.           u += j;//加上分解的长度
    
81.           if (k[u] < 0)
    
82.             k[u] = i;
    
83.           else
    
84.             k[u] = min(k[u], i);
    
85.         }
    
86.       }
    
87.     }
    
88.   }
    
89.   //排序和去重
    
90.   sort(k, k + N + 1);
    
91.   auto itr_end = unique(k, k + N + 1);
    
92.   //求和
    
93.   long long nSum = 0;
    
94.   for (auto itr = k; itr != itr_end; ++itr)
    
95.     nSum += *itr;
    
96.   cout << nSum << endl;
    
97.   return 0;
    
98. }

复制代码