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

import math

def factorize(n):
        f = []
        d = 2
        bound = math.sqrt(n)
        while d <= bound and n > 1:
                if n % d == 0:
                        f.append(d)
                        n = n / d
                else:
                        d = d + 1
        if n > 1:
                f.append(n)
        return f

def factorizations(n):
        f = factorize(n)
        sol = set()
        sol.add(tuple())
        for p in f:
                prev = sol
                sol = set()
                for pf in prev:
                        sol.add(tuple(sorted(pf + (p, ))))
                        t = list(pf)
                        for i in range(len(t)):
                                t[i] *= p
                                sol.add(tuple(sorted(t)))
                                t[i] /= p
        return sol

kmax = 12000
mpsn = [ None ] * (kmax + 1)
rem = kmax - 1

n = 2
while rem > 0:
        for nf in factorizations(n):
                no = n - sum(nf) # number of ones
                k = no + len(nf)
                if k < 2 or k > kmax:
                        continue
                elif mpsn[k] is None:
                        mpsn[k] = n
                        rem -= 1
                
        n += 1
        
mpsns = set(mpsn[2:])
print 'sum of minimal product-sum numbers:', sum(mpsns)
print 'max. number is', n - 1

fc1735

mem = []
used = set()
k = set(range(2, 12001))
for n in range(9999999999999999):
  mem.append(set())
  if len(k) == 0:
    break
  for p in range(2, 999999999999999999999):
    if p * p > n:
      break
    if n % p != 0:
      continue
    d = n // p
    for i in mem[d]:
      mem[n].add(i + n - p - d + 1)
  mem[n].add(1)
  for i in mem[n]:
    if i in k:
      k.remove(i)
      used.add(n)

print(sum(used))

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

guosl

/*
答案：7587456
耗时：0.671572秒
*/
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <cstring>
using namespace std;

const int N = 12000;//欲求的范围
const int M = 24000;//计算的范围

int k[N + 1];//记录要求的结果
int fp[M];//fp[i]记录i的最小素因数
int pc[M];//记录i的素因数个数

/*
对x进行分解为nc个因数的乘积
int nc 分解的因数个数
int x 要被分解的数
int nS 前面已经分解的因数和
vector<int> &v 记录整个分解的因数之和
*/
void dfs(int nc, int x, int nS, vector<int> &v)//递归计算分解
{
  if (nc == 1)//分解结束
  {
    v.push_back(nS + x);
    return;
  }
  if (fp[x] == x)//x是素数无法分解
    return;
  for (int i = fp[x]; i <= (int)sqrt((double)x); ++i)//枚举x的可能因数
  {
    if (x%i == 0)
      dfs(nc - 1, x / i, nS + i, v);//继续下去
  }
}

int main(void)
{
  memset(k, -1, sizeof(k));//将k都预置为-1
  //应用筛法求每个数的最小素数数
  for (int i = 1; i < M; ++i)
    fp[i] = i;
  for (int i = 2; i <= (int)sqrt((double)M); ++i)
  {
    if (fp[i] < i)
      continue;
    for (int j = i*i; j < M; j += i)
      fp[j] = min(fp[j], i);
  }
  //计算每个数的素因数个数
  for (int i = 2; i < M; ++i)
  {
    int x = i;
    while (x > 1)
    {
      int y = fp[x];
      x /= y;
      ++pc[i];
    }
  }
  //计算k
  for (int i = 4; i < M; ++i)
  {
    if (fp[i] == i)//素数肯定不是和积数
      continue;
    for (int j = 2; j <= pc[i]; ++j)
    {
      vector<int> v;
      dfs(j, i, 0, v);//对i进行长度为j的因数分解
      for (auto itr = v.begin(); itr != v.end(); ++itr)//对不同的分解计算k
      {
        int u = i - *itr;//计算积与和的差，补上上这些1就成了和积数
        if (u >= 0 && u <= N)
        {
          u += j;//加上分解的长度
          if (k[u] < 0)
            k[u] = i;
          else
            k[u] = min(k[u], i);
        }
      }
    }
  }
  //排序和去重
  sort(k, k + N + 1);
  auto itr_end = unique(k, k + N + 1);
  //求和
  long long nSum = 0;
  for (auto itr = k; itr != itr_end; ++itr)
    nSum += *itr;
  cout << nSum << endl;
  return 0;
}