题目

Problem 615. The millionth number with at least one million prime factors

新葡京娱乐场:滴滴对由此给用户带来的等待时间过长等体验不佳表示歉意。

Consider the natural numbers having at least 5 prime factors, which don't have to be distinct.
Sorting these numbers by size gives a list which starts with:

32 = 2?2?2?2?2
48 = 2?2?2?2?3
64 = 2?2?2?2?2?2
72 = 2?2?2?3?3
80 = 2?2?2?2?5
96 = 2?2?2?2?2?3
...

So, for example, the fifth number with at least 5 prime factors is 80.

Find the millionth number with at least one million prime factors.
Give your answer modulo 123454321.

题解

第615题:第一百万个拥有至少一百万个素因数的数

考虑拥有至少 5 个素因数的自然数,这些素因数不必不同。
将这些数从小到大排序,得到以下列表:

32 = 2?2?2?2?2
48 = 2?2?2?2?3
64 = 2?2?2?2?2?2
72 = 2?2?2?3?3
80 = 2?2?2?2?5
96 = 2?2?2?2?2?3
...

例如,第 5 个拥有至少 5 个素因数的数是 80。

找出第一百万个拥有至少一百万个素因数的数。
将你的答案对 123454321 取余。

分析

令 A = 21000000,则拥有至少一百万个素因数的数按顺序是:

  • A1 = A
  • A2 = A × 3/2
  • A3 = A × 2 = A1 × 2
  • A4 = A × 32/22
  • A5 = A × 5/2
  • A6 = A × 3/2 × 2 = A2 × 2
  • A7 = A × 33/23
  • A8 = A × 7/2
  • A9 = A × 3×5/22
  • A10 = A × 22 = A1 × 22
  • A11 = A × 32/22 × 2 = A4 × 2
  • A12 = A × 5/2 × 2 = A5 × 2
  • A13 = A × 34/24
  • A14 = A × 3×7/22
  • A15 = A × 11/2
  • A16 = A × 32×5/23
  • A17 = A × 3/2 × 22 = A2 × 22
  • A18 = A × 52/22
  • A19 = A × 13/2
  • A20 = A × 33/23 × 2 = A7 × 2
  • ……

这些数分为两类:

  1. 素因数的个数等于一百万(黑色),这由 A 乘以 m 个素数,然后除以 2m(m ≥ 0)得到。
  2. 素因数的个数大于一百万(红色),这由第 1 类数乘以 2n(n > 0)得到。

因此,我们只需要生成所有不超过某个上限的这两类数,然后进行排序,再取第一百万个数即可。

以 n = 20 为例,具体计算过程如下所示:

解答

根据以上分析,我们有以下 C# 程序:

 1: using System;
 2: using System.Numerics;
 3: using System.Collections.Generic;
 4: using Skyiv.Utils;
 5: 
 6: static class E615
 7: {
 8:  static readonly int m = 123454321, n = (int)1e6, z = (int)2e5;
 9:  static readonly int[] primes = Primes.GetPrimes(0, z);
10:  static readonly double max = primes[primes.Length - 1] / 2.0;
11:  static readonly List<double> list = new List<double>();
12: 
13:  static void Make(double u, int i0)
14:  {
15:   double v = u; for (; v <= max; v *= 2) list.Add(v);
16:   for (var i = i0; i < primes.Length &&
17:    (v = u * primes[i] / 2) <= max; i++) Make(v, i);
18:  }
19: 
20:  static Tuple<long, int> Tran(double u)
21:  { // return: (a, b): u == a / 2^b
22:   for (var i = 0; ; i++, u *= 2)
23:    if (Math.Abs(Math.Round(u) - u) < 1e-3)
24:     return Tuple.Create((long)Math.Round(u), i);
25:  }
26: 
27:  static void Main()
28:  {
29:   Make(1, 1); list.Sort(); var t = Tran(list[n - 1]);
30:   Console.WriteLine(BigInteger.ModPow(2, n-t.Item2, m) * t.Item1 % m);
31:  }
32: }

简要说明:

  • 第 9 行的 GetPrimes 方法见参考资料1。
  • 第 11 行的 list 用于存放上述的两类数。存放的是除以 A 之后的数(double 类型),是分母为 2m(m ≥ 0) 的分数。
  • 第 8 行的 z 和第 10 行的 max 用于决定生成的数的上限。如果这个值取得太小,会导致生成的数不够一百万个,从而在第 29 行(list[n - 1])抛出异常。如果取得太大,会增大这个程序的运行时间。
  • 第 13 至 18 行的 Make 方法用于生成这两类数。
  • 第 15 行的循环,加入 list 的第 1 个数是第 1 类数,其余的是第 2 类数。
  • 第 16 至 17 行的循环递归地生成所有不超过上限的数。
  • 第 20 至 25 行的 Tran 函数从 double 得到分子和分母。
  • 第 29 行首先生成这两类数,然后排序,再取第一百万个数。
  • 第 30 行通过乘以 A 得到最终答案。

这个程序的运行时间是 0.4 秒。

参考资料

  1. 图灵社区:使用筛法生成素数