150523

Ruby


2〜Nまでをある規則にしたがって並びかえる

次のような2〜Nの小さい順の並びとあまり変わらない並びかえを
思いついた。

require 'prime'

N = 100
ary = []
h = {}
(2..N).each{|i|
  if i.prime?
    ary.push(h.values)
    p h # 検証用の出力なので省いても構わない
    h = {1 => [i]}
  else
    s = 0
    i.prime_division.map{|j| s += j[1]}
    h.key?(s) ? h[s] = h[s].push(i) : h[s] = [i] # sは1, 2, … とは限らない
  end
}
p ary.push(h.values).flatten

出力結果
{}
{1=>[2]}
{1=>[3], 2=>[4]}
{1=>[5], 2=>[6]}
{1=>[7], 3=>[8], 2=>[9, 10]}
{1=>[11], 3=>[12]}
{1=>[13], 2=>[14, 15], 4=>[16]}
{1=>[17], 3=>[18]}
{1=>[19], 3=>[20], 2=>[21, 22]}
{1=>[23], 4=>[24], 2=>[25, 26], 3=>[27, 28]}
{1=>[29], 3=>[30]}
{1=>[31], 5=>[32], 2=>[33, 34, 35], 4=>[36]}
{1=>[37], 2=>[38, 39], 4=>[40]}
{1=>[41], 3=>[42]}
{1=>[43], 3=>[44, 45], 2=>[46]}
{1=>[47], 5=>[48], 2=>[49, 51], 3=>[50, 52]}
{1=>[53], 4=>[54, 56], 2=>[55, 57, 58]}
{1=>[59], 4=>[60]}
{1=>[61], 2=>[62, 65], 3=>[63, 66], 6=>[64]}
{1=>[67], 3=>[68, 70], 2=>[69]}
{1=>[71], 5=>[72]}
{1=>[73], 2=>[74, 77], 3=>[75, 76, 78]}
{1=>[79], 5=>[80], 4=>[81], 2=>[82]}
{1=>[83], 4=>[84, 88], 2=>[85, 86, 87]}
{1=>[89], 4=>[90], 2=>[91, 93, 94, 95], 3=>[92], 6=>[96]}
[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23,
 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43,
 44, 45, 46, 47, 48, 49, 51, 50, 52, 53, 54, 56, 55, 57, 58, 59, 60, 61, 62, 65,
 63, 66, 64, 67, 68, 70, 69, 71, 72, 73, 74, 77, 75, 76, 78, 79, 80, 81, 82, 83,
 84, 88, 85, 86, 87, 89, 90, 91, 93, 94, 95, 92, 96, 97, 98, 99, 100]