Chokudai Contest002 解法

問題概要

10⁹以下の整数を100個出力しろ。出力した数の約数の集合(重複は除く)の数が多いほど良い。

コメント

本番では高度合成数を適当にいくつか出力するくらいしか分からなかった。

のでTLに流れてた回答を見て解いた。解法１を本番中に思いつきたかった...

コンテストページ

Chokudai Contest 002 - Chokudai Contest 002 | AtCoder

解法

解法1：高度合成数×素数

約数が多い高度合成数に異なる素数をかけて結果が10⁹を超えないものを出力。

すると250-1000個程度の約数をもつ高度合成数が選ばれるので35000-40000くらいの点数が出る

提出コード：Submission #965609 - Chokudai Contest 002 | AtCoder

ヒント２：
高度合成数、ってすごい約数が多い数があるらしいぞ！
例えば720720とかあったとしよう。これに適当な素数を掛けた場合、29を掛けた数、31を掛けた数、37を掛けた数……とかを考えたら、約数はいくつ出来るかな？和集合は？
#chokudai_002

— chokudai(高橋 直大) (@chokudai) November 3, 2016

解法2：約数が多い数を10000個ほど挙げて焼きなまし

色々調べながらやってみた
コード：https://gist.github.com/SoichiSumi/34fb428b9b07a2f6d8df209f35087d36

9e8 以上の整数を約数の個数が多い順に1万個くらい列挙して、焼きなました#chokudai_002

— えいたほ (@eitaho) November 3, 2016