欧拉项目 124题 | 求有序根函数的第k个元素

欧拉项目的124题题意是：
n的根函数，rad(n)，定义为其所有不同质因子之积。例如，504 = 2^3 + 3^2 * 7, 所以 rad(504) = 2 * 3 * 7 = 42
令E(k)是求得了前n个rad(n)之后排序，第k个所对应的n。
n从1到100000，求得rad(n)，问题是要求E(10000)。

这道题的第一步是分解质因数。
为此，我先生成了一个数组primes，放了从1到10万中的质数部分，从小到大排列，这很重要。
下面是分解质因数的代码：

private static long[] TrialDivisioFac(long n)
{
    List<long> results = new List<long>();
    int index = 0;
    while (primes[index] <= n)
    {
        while (n % primes[index] == 0)
        {
            results.Add(primes[index]);
            n /= primes[index];
        }
        index++;
    }

    return results.ToArray();
}

原理很简单，从最小的质数2除起，内层的while保证小的质因数都被加到结果集中，再去判断下一个质数是不是该数的质因数。

拿到所有的质因数之后，调用Distinct函数，然后求积就可以得到对应的rad。

对rad n排序，为了简单起见，我把n和rad n打包在一起，并且实现了IComparable，便于之后的排序。排序规则是以rad为主键，rad一样的情况下，按照n排序。

public class NAndRadN : IComparable
{
    public int n;
    public long rad;

    public int CompareTo(object that)
    {
        var t = that as NAndRadN;
        if (this.rad == t.rad)
        {
            return this.n.CompareTo(t.n);
        }
        else
        {
            return this.rad.CompareTo(t.rad);
        }
    }
}

准备工作做好之后，写一个for循环，把1到10万的rad算出来。排序，找到第1万个数字，输出即可。

for (long i = 1; i <= 100000; i++)
{
    long[] fac = TrialDivisioFac(i).Distinct().ToArray();
    long p = 1;
    foreach (var f in fac)
    {
        p *= f;
    }

    results.Add(new NAndRadN { n = (int)i, rad = p });
}

var rads = results.ToArray();
Array.Sort(rads);
return rads[9999].n;