欧拉项目 #21

Question

欧拉项目 #21

4

条件:

定义 d(n) 为 n 的真因数之和（小于n的能整除n的所有正整数）。如果存在 a 和 b，满足 d(a) = b, d(b) = a 且 a ≠ b，则称 a 和 b 是一对亲和数，并且它们中的每一个都被称为亲和数。

例如，220 的真因数为 1、2、4、5、10、11、20、22、44、55 和 110；因此 d(220) = 284。284 的真因数为 1、2、4、71 和 142；所以 d(284) = 220。

计算出所有 10000 以内的亲和数之和。

我做了以下事情：

    static void Main()
    {
        long sum = 0;
        List<int> passedValues = new List<int>();
        for (int i = 1; i < 10000; i++)
        {
            var number1 = SumOfNumber(i);
            var number2 = SumOfNumber(SumOfNumber(i));
            if (number2 == i && !passedValues.Contains(number1))
            {
                sum = sum + number1;
                passedValues.Add(number1);
                passedValues.Add(number2);
            }
        }
        Console.WriteLine(sum);
        Console.ReadKey();
    }

    private static int SumOfNumber(int input)
    {
        int sum = 0;
        for (int i = 1; i <= input/2; i++)
        {
            if (input%i == 0)
            {
                sum += i;
            }
        }
        return sum;
    }

然而，我的程序给出的结果是40284，而正确答案似乎应该是31626。为什么我的程序不能正常工作？我是否重复添加了某些内容？我还尝试过添加一个列表来存储已传递的值，但最终结果却是25008：

static void Main()
    {
        long sum = 0;
        List<int> passed = new List<int>();
        for (int i = 1; i < 10000; i++)
        {
            var number1 = SumOfNumber(i);
            var number2 = SumOfNumber(SumOfNumber(i));
            if (number2 == i && !passed.Contains(i))
            {
                sum = sum + number1;
                passed.Add(number1);
            }
        }
        Console.WriteLine(sum);
        Console.ReadKey();
    }

- KOPEUE

http://www.mathblog.dk/project-euler-21-sum-of-amicable-pairs/ - Vadim Martynov

3

如果我想复制粘贴一些代码，但不想在这里发布以寻求帮助。 - KOPEUE

简单来说，你的代码没有解决问题。逐步执行它，你会发现为什么。你应该在不到十次 F10 按键的情况下找到罪犯。 - SimpleVar

4个回答

4

我得到的结果是31626。这里的区别在于如何防止求和中出现重复。不要将结果保存到列表中，只需确保i始终小于number1即可。

 static void Main()
    {

        long sum = 0;
        List<int> passedValues = new List<int>();
        for (int i = 1; i < 10000; i++)
        {
            var number1 = SumOfNumber(i);
            var number2 = SumOfNumber(SumOfNumber(i));


            if (number2 == i && i < number1)
            {
                sum = sum + i + number1;

            }
        }
        Console.WriteLine(sum );
        Console.ReadKey();
    }

    private static int SumOfNumber(int input)
    {
        int sum = 0;
        for (int i = 1; i <= input / 2; i++)
        {
            if (input % i == 0)
            {
                sum += i;
            }
        }
        return sum;
    }

- George Chen

这也是一个很好的解决方案，既避免了完美数，又很好地避免了重复！干杯 :) - mellamokb

0

private static int SumOfNumber(int input)
{
    int sum = 0;
    for (int i = 1; i <= input/2; i++)
    {
        if (input%i == 0)
        {
            sum += i;
        }
    }
    return sum;
}

这不是正确的。你只添加了一个因子，而没有循环到该数字的平方根。

- cubesnyc

0

顺便说一下，另一个算法是先分解质因数，然后通过对因子及其幂次的映射进行递归，找到所有可能的除数。

当 n 变大时，例如 n = 100_000，这种方法可以更快。

代码（`go`）

amicable_number.go:

package p21

import (
    "math"
)

// refer:   https://projecteuler.net/problem=21
/*
Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.
*/
// find sum of all amicable numbers < n
func FindAmicableNumberSum(n int, excludeSame bool) int {
    dm := FindAmicableNumber(n, excludeSame)
    sum := 0
    for k, v := range dm {
        if k != v {
            sum += k
        }
    }
    return sum
}

// find all amicable numbers < n, in map's key, map's value is the other pair,
func FindAmicableNumber(n int, excludeSame bool) map[int]int {
    dsm := FindAllDivisorSum(n)
    am := make(map[int]int)
    for k, v := range dsm {
        if v2, ok := dsm[v]; ok && k == v2 {
            if excludeSame && k == v {
                continue
            }
            am[k] = v
            am[v] = k
        }
    }
    return am
}

// find divisor sum for all number x < n, divisor include 1, exclude x itself,
func FindAllDivisorSum(n int) map[int]int {
    ps := FindPrimeTillN(n + 1)
    dm := make(map[int]int)
    for x := 2; x < n; x++ {
        ks, fm := findFactorMap(x, ps)
        sum := divisorSum(ks, fm) - x
        dm[x] = sum
    }
    return dm
}

// find divisor sum of x, divisor include 1, exclude x itself,
func FindDivisorSum(x int) int {
    ps := FindPrimeTillN(x + 1)
    ks, fm := findFactorMap(x, ps)
    return divisorSum(ks, fm) - x
}

// factorize x, with given prime cache,
func findFactorMap(x int, ps []int) ([]int, map[int]int) {
    fm := make(map[int]int)
    var ks []int
    for i := 0; i < len(ps) && x > 1; i++ {
        p := ps[i]
        e := 0
        for x%p == 0 {
            x /= p
            e++
        }
        if e > 0 {
            ks = append(ks, p)
            fm[p] = e
        }
    }
    return ks, fm
}

// sum of all divisor, include 1 and x itself,
// tip:
// - to avoid clone of ks slice & fm map, and keep 2 branch don't affect each other,
//   should recover ks slice & fm map before return,
//   thus ks & fm are not change after calling the function,
func divisorSum(ks []int, fm map[int]int) int {
    // fmt.Printf("%v, %v\n", ks, fm)
    if len(ks) == 1 {
        p := ks[0]
        e := fm[p]
        sum := 1
        for i, d := 1, p; i <= e; i, d = i+1, d*p {
            sum += d
        }
        return sum
    }

    fp := ks[0]
    fe := fm[fp]
    if fe == 0 { // x=0, formula: f(a^0 * ..) = f(..)
        delete(fm, fp)
        result := divisorSum(ks[1:], fm)
        fm[fp] = fe // recover
        return result
    } else if fe == 1 { // x=1, formula: f(a^1 * ..) = (a+1) * f(..)
        delete(fm, fp)
        result := (fp + 1) * divisorSum(ks[1:], fm)
        fm[fp] = fe // recover
        return result
    } else { // x>=2, formula: f(a^x * ..) = a^x * f(..) + f(a^(x-1) * ..)
        fm[fp]--
        right := divisorSum(ks, fm)
        fm[fp]++ // recover

        delete(fm, fp)
        left := int(math.Pow(float64(fp), float64(fe))) * divisorSum(ks[1:], fm)
        fm[fp] = fe // recover

        return left + right
    }
}

// find all primes < n
func FindPrimeTillN(n int) []int {
    var ps []int
outer:
    for x := 2; x < n; x++ {
        max := int(math.Sqrt(float64(x)))
        for i := 0; i < len(ps) && ps[i] <= max; i++ {
            if x%ps[i] == 0 {
                continue outer
            }
        }
        ps = append(ps, x)
    }
    return ps
}

amicable_number_test.go (测试用例):

package p21

import (
    "fmt"
    "github.com/stretchr/testify/assert"
    "testing"
)

func TestFindAmicableNumberSum(t *testing.T) {
    sumExcludeSame := FindAmicableNumberSum(10_000, false)
    fmt.Printf("10000 (include same = %v) -> sum: %d\n", false, sumExcludeSame)
    assert.Equal(t, 31626, sumExcludeSame)
}

func TestFindAmicableNumberSumLarge(t *testing.T) {
    // n = 100_000, takes 1s,
    // fmt.Printf("100_000 (include same = %v) -> sum: %d\n", false, FindAmicableNumberSum(100_000, false))

    // n = 1_000_000, takes 57s,
    // fmt.Printf("1_000_000 (include same = %v) -> sum: %d\n", false, FindAmicableNumberSum(1_000_000, false))
}

func TestFindAmicableNumber(t *testing.T) {
    fmt.Printf("10_000 (include same = %v) -> pairs: %d\n", true, FindAmicableNumber(10_000, true))
    fmt.Printf("10_000 (include same = %v) -> pairs: %d\n", false, FindAmicableNumber(10_000, false))
}

func TestFindDivisorSum(t *testing.T) {
    fmt.Printf("30 -> %d\n", FindDivisorSum(30))
    fmt.Printf("220 -> %d\n", FindDivisorSum(220))
    fmt.Printf("284 -> %d\n", FindDivisorSum(284))
    fmt.Printf("1184 -> %d\n", FindDivisorSum(1184))
    fmt.Printf("1210 -> %d\n", FindDivisorSum(1210))
}

要运行测试，需要通过以下方式添加testify：

go get -u github.com/stretchr/testify

速度

这比问题中使用的蛮力方法要快得多，以下是我的测试结果（在一台旧笔记本上运行）：

使用分解因数和递归（即上面的代码）：
- n = 10_000，sum = 31626，耗时0.02秒。
- n = 100_000，sum = 852810，耗时0.97秒。
- n = 1_000_000，sum = 25275024，耗时57秒。
  我认为它可以进一步优化，因为对于1_000_000来说仍然很慢。
使用暴力方法（即与问题中类似的代码）：
- n = 10_000，sum = 31626，耗时0.38秒。
- n = 100_000，sum = 852810，耗时38秒。
- n = 1_000_000，时间太长，我在完成之前停止了。

提示

函数FindAmicableNumberSum()接受一个标志excludeSame，用于指示是否排除使d(n) = n的数字。
对于Project Euler＃21，它应始终设置为true。

- Eric

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- mellamokb · Accepted Answer

这里有两个问题:

您没有将两个友好数对的数字都加入到总和中。
您包括完美数(其中d(n) = n)，这些不符合友好数对的资格，因为违反了a ≠ b。

我认为您在不添加列表以存储经过的数字时更接近了解决问题#1，因为它导致仅添加number1的贡献到总和，但添加number1和number2到列表中，最终导致跳过number2。为解决问题#2，您还需要验证number1 != number2。例如:

if (number2 == i && number1 != number2)
                 ^^^^^^^^^^^^^^^^^^^^^ add this check
{
    sum = sum + i;

在对您提供的代码进行这两项修复后，我得到了预期的总数31626。

欧拉项目 #21

代码（go）

速度

提示

代码（`go`）