(ΦωΦ)＜高度合成数一覧の出力に優先度つきキューを使う

「競プロ!!」競技プログラミング Advent Calendar 2017 5 日目の記事です。
タイトルが日本語になって、分かりやすくていいですね。
今までの名前の方もあるんですけどね。解説も。

---
$10^{18}$ 未満の高度合成数の一覧を出力することを考えます。
※高度合成数とは?
ある正整数が、それ未満のどの正整数よりも約数の個数が多いとき、その正整数を高度合成数といいます。要するに約数がめっちゃ多い正整数のことです。

高度合成数の一覧を出力する上で、優先度つきキューを使う方法があります。
概要は下の枠内のようになります。
前提として、約数の個数は素因数分解したときの素数ごとの羃をそれぞれ +1 してから掛け算すれば求められるという知識は入れといてください。
+1 するのは $0$ 乗の分を数えるからですね。

まず、素数を篩などで列挙しておく。
約数の個数を第一優先度とする優先度つきキューに、「約数の個数」「値そのもの」「何番目の素数を」「何個使ったか」という四属性をオブジェクトにして詰める。
キューを詰めていく方向は二つで、「(A) 今見ている素数をもうひとつ増やす」か「(B) 次の素数を新たにひとつ使う」かになる。
A の場合、$i$ 番目の素数が $icnt$ 個から $icnt+1$ 個になるとき、約数の個数は $\displaystyle \frac{icnt+2}{icnt+1}$ 倍になり、
B の場合、約数の個数は $2$ 倍になる。

Python による実装を掲載しておきます。$10^{18}$ 未満だと ideone で五秒程度です。
値 $x$ について対数を取るなどの工夫をすれば C 言語系などでも上手く書けて、高速化が見込めるでしょう。

#!/usr/bin/python3
# -*- coding: utf-8 -*-
# †
from collections import namedtuple
from heapq import heappush, heappop
Tup = namedtuple('Tup', 'cnt, num')

def sieve(N):
    is_prime = [False, False] + [True] * (N-1)
    sq = int(N ** .5)
    for i in range(2, sq+1):
        if is_prime[i]:
            for j in range(i*i, N+1, i):
                is_prime[j] = False
    return [i for i, p in enumerate(is_prime) if p]

primes = sieve(50)
N = len(primes)
LIMIT = 10**18

pq = []
cnt = 1
x = 1
# 約数の個数、値そのもの、i番目の素数を、icnt個使う
heappush(pq, (cnt, x, 0, 0))
max_cnt = cnt
resArr = []
while len(pq):
    cnt, x, i, icnt = heappop(pq)
    if max_cnt < cnt:
        resArr.append(Tup(cnt, x))
        max_cnt = cnt
    if x * primes[i] < LIMIT:
        # i 番目を icnt 個から 1 個増やして icnt+1 個にする
        heappush(pq, (cnt*(icnt+2)//(icnt+1), x*primes[i], i, icnt+1))
    if i + 1 < N and x * primes[i+1] < LIMIT:
        # i+1 番目を新たに 1 個使う
        heappush(pq, (cnt*2, x*primes[i+1], i+1, 1))

# 値で昇順になるように情報をオミットして出力する。
resArr.sort(key=lambda tup: tup.num)
max_cnt = 0
for cnt, num in resArr:
    if max_cnt < cnt:
        max_cnt = cnt
        # 約数の個数, 値
        print(cnt, num)

(ΦωΦ)＜おしまい