2からNまでを、素因数分解したときの素因数の最小値が小さい順に並べるには？


2 = 2^1  
3 = 2^0 * 3^1  
4 = 2^2  
5 = 2^0 * 3^0 * 5^1  
6 = 2^1 * 3^1  
7 = 2^0 * 3^0 * 5^0 * 7^1  
8 = 2^3  
9 = 2^0 * 3^1  
10 = 2^1 * 3^0 * 5^1  
となるので、

2から10までを  
素因数分解したときに含まれる素因数の最小値が小さい順に  
（ただし、  
m, n の最小の素因数が同じ場合、  
その次数が小さい方が先とする。  
また、m, n の最小の素因数が同じでなおかつその次数が同じ場合、  
大きさが小さい方が先とする。）  
並べると、[2, 6, 10, **4** , **8** , 3, **9** , 5, 7] となる。

さて、一般のNに対し、この規則に従い2からNまでを並びかえを行うには  
どうすればよろしいでしょうか？

（追記）  
上記条件の説明を加えておきます。  
70 = 2^1 * 3^0 * 5^1 * 7^1 * 11^0 * 13^0  
78 = 2^1 * 3^1 * 5^0 * 7^0 * 11^0 * 13^1  
なので、  
「この二つに数について、最小の素因数が同じでなおかつその次数が同じ場合」  
にあたる。  
70 < 78 より、70 が先となる。




(最小素因数のループ)☓(次数のループ) にすれば、ソート・篩分けなしでできます。しかも、素数列さえ持っていれば `%` (剰余) による判定も不要です。

**Ruby コード** :

[code]

    #!/usr/bin/env ruby
    require 'prime'
    include Math
    
    def special_ordering(n)
      mark = {}
      Prime.each(n).map{|prime| # 最小素因数のループ(昇順)
        log(n, prime).round.downto(1).map{|order| # 次数のループ(降順)
          (modulo = prime ** order).step(n, modulo).select{|m|
            mark[m] = 1 unless mark[m] # 既に出力した物は除外
          }
        }.reverse
      }.flatten
    end
    
    p special_ordering(70)
    
[/code]

**説明** :

最小素因数とその次数が (p, k) である様な整数は pk の倍数になっています。従って、ループの中で pk の倍数を生成して、その後で実際に (p,
k) が最小素因数とその次数になっているかで篩いにかけます。

ここで、(p, k) のループの回し方を工夫します。或る整数 i を倍数として生成する (p, k):  
(p, k) s.t. ∃m∈ **N** , i = m pk  
の内、整数 i の最小素因数とその次数になっているのは、「最小の p を持つ物の内の更に最大の k を持つ物」になります。従って、外のループで p
を昇順にして、内側のループで k を降順にすると、その整数が初めて生成された時の (p, k)
が最小素因数とその次数になっています。つまり、その整数が初めて生成された時に結果に登録すれば良いのです。

但し、次数を降順で回したので、後で各次数についての結果を逆順にして繋げる必要があります(上記コードの `.reverse` の部分)。

**出力** :  
[2, 6, 10, 14, 18, 22, 26, 30, 34, 38, 42, 46, 50, 54, 58, 62, 66, 70, 4, 12,
20, 28, 36, 44, 52, 60, 68, 8, 24, 40, 56, 16, 48, 32, 64, 3, 15, 21, 33, 39,
51, 57, 69, 9, 45, 63, 27, 5, 35, 55, 65, 25, 7, 49, 11, 13, 17, 19, 23, 29,
31, 37, 41, 43, 47, 53, 59, 61, 67]

* * *

編集: 中で何をやっているかの説明を追加しました。




(最小素因数のループ)☓(次数のループ) にすれば、ソート・篩分けなしでできます。しかも、素数列さえ持っていれば `%` (剰余) による判定も不要です。

**Ruby コード** :

[code]

    #!/usr/bin/env ruby
    require 'prime'
    include Math
    
    def special_ordering(n)
      mark = {}
      Prime.each(n).map{|prime| # 最小素因数のループ(昇順)
        log(n, prime).round.downto(1).map{|order| # 次数のループ(降順)
          (modulo = prime ** order).step(n, modulo).select{|m|
            mark[m] = 1 unless mark[m] # 既に出力した物は除外
          }
        }.reverse
      }.flatten
    end
    
    p special_ordering(70)
    
[/code]

**説明** :

最小素因数とその次数が (p, k) である様な整数は pk の倍数になっています。従って、ループの中で pk の倍数を生成して、その後で実際に (p,
k) が最小素因数とその次数になっているかで篩いにかけます。

ここで、(p, k) のループの回し方を工夫します。或る整数 i を倍数として生成する (p, k):  
(p, k) s.t. ∃m∈ **N** , i = m pk  
の内、整数 i の最小素因数とその次数になっているのは、「最小の p を持つ物の内の更に最大の k を持つ物」になります。従って、外のループで p
を昇順にして、内側のループで k を降順にすると、その整数が初めて生成された時の (p, k)
が最小素因数とその次数になっています。つまり、その整数が初めて生成された時に結果に登録すれば良いのです。

但し、次数を降順で回したので、後で各次数についての結果を逆順にして繋げる必要があります(上記コードの `.reverse` の部分)。

**出力** :  
[2, 6, 10, 14, 18, 22, 26, 30, 34, 38, 42, 46, 50, 54, 58, 62, 66, 70, 4, 12,
20, 28, 36, 44, 52, 60, 68, 8, 24, 40, 56, 16, 48, 32, 64, 3, 15, 21, 33, 39,
51, 57, 69, 9, 45, 63, 27, 5, 35, 55, 65, 25, 7, 49, 11, 13, 17, 19, 23, 29,
31, 37, 41, 43, 47, 53, 59, 61, 67]

* * *

編集: 中で何をやっているかの説明を追加しました。

