题目124：求有序根函数的第k个元素

欧拉计划

Ordered radicals

The radical of n, rad(n), is the product of the distinct prime factors of n. For example, 504 = 2³ × 3² × 7, so rad(504) = 2 × 3 × 7 = 42.

If we calculate rad(n) for 1 ≤ n ≤ 10, then sort them on rad(n), and sorting on n if the radical values are equal, we get:

Let E(k) be the kth element in the sorted n column; for example, E(4) = 8 and E(6) = 9.

If rad(n) is sorted for 1 ≤ n ≤ 100000, find E(10000).

题目：

n 的根函数，rad(n)，定义为其所有不同质因子之积。例如，504 = 2³ × 3² × 7，所以 rad(504) = 2 × 3 × 7 = 42。

如果我们对 1 ≤ n ≤ 10 计算 rad(n)，然后先根据 rad(n) 的值排序，如果 rad 值相同再根据 n 排序，我们得到：

令 E(k) 为排序之后的第 k 个 n 值，例如， E(4) = 8， E(6) = 9。

如果将 1 ≤ n ≤ 100000 的 rad(n) 按照上述方法排序，求 E(10000)。

jerryxjr1220

解答：

#coding:utf-8
plist = []
primes = [True] * 100000
primes[0], primes[1] = False, False
for i, prime in enumerate(primes):
    if prime:
        for j in range(i * i, 100000, i):
            primes[j] = False
for i, prime in enumerate(primes):
    if prime:
        plist.append(i)
def rad(n):
    rlist = []
    for p in plist:
        if n % p == 0:
            rlist.append(p)
            n //= p
        if n < p:
            break
    s = 1
    for e in rlist:
        s *= e
    return s

order = [(1,1)]
for i in range(2,100001):
    order.append((rad(i),i))
order.sort()
print (order[9999])

输出：
21417

guosl

//21417
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

struct stNode
{
  int idx;
  int r;
  bool operator<(const stNode &n) const
  {
    if (r != n.r)
      return (r < n.r);
    else
      return (idx < n.idx);
  }
};

stNode np[100001];
char cp[100001];

int main(void)
{
  memset(cp, 1, sizeof(cp));
  for (int i = 1; i <= 100000; ++i)
  {
    np[i].idx = i;
    np[i].r = 1;
  }
  cp[0] = 0;
  cp[1] = 0;
  for (int i = 2; i <= 317; ++i)
  {
    if (cp[i] == 0)
      continue;
    for (int j = i * i; j <= 100000; j += i)
      cp[j] = 0;
  }
  for (int i = 2; i <= 100000; ++i)
  {
    if (cp[i] == 1)
    {
      for (int j = i; j <= 100000; j += i)
        np[j].r *= i;
    }
  }
  sort(np, np + 100001);
  cout << np[10000].idx << endl;
  return 0;
}