10491


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 が先となる。


CC BY-SA 3.0
2015-05-20T22:29:36.467
10436
2015-07-09T20:06:16.807
2015-05-21T15:20:33.060
5363
5363
question
アルゴリズム
2からNまでを、素因数分解したときの素因数の最小値が小さい順に並べるには？


何のひねりも無くPythonで書いてみました。素因数`p`を含む数の集合`s`とそれ以外に分割し、`s`を次数昇順でソートしています。

[code]

    def solve(n):
        l = list(range(2, n+1))
        r = []
        while l:
            # prime factor
            p = l[0]
            # split list
            s = [i for i in l if i % p == 0]
            for i in s:
                l.remove(i)
            # sort by factor count
            def cmp_key(i):
                c = 0
                while i % p == 0:
                    i /= p
                    c += 1
                return c
            s.sort(key=cmp_key)
            r.extend(s)
        return r
    
    print(solve(10))
    # [2, 6, 10, 4, 8, 3, 9, 5, 7]
    
[/code]


CC BY-SA 3.0
2015-05-21T00:37:25.553
10439
2015-05-21T13:33:52.487
2015-05-21T13:33:52.487
49
49
10436
answer


Rubyで書いてみました。答えを順番に探して加えていく単純な方法です。

[code]

    require 'prime'
    
    N = 70
    mark = {}
    ary = []
    Prime.each(N){|i|
      # 素数iで初めて割り切れる数をtmpに加えていく
      tmp = []
      i.step(N, i){|j|
        if mark[j] == nil
          tmp.push(j) 
          mark[j] = 1
        end
      }
      # 次数が低い順にaryに加える
      f_ary, b_ary = tmp, []
      j = i * i
      while f_ary.size > 0
        f_ary.each{|k| k % j == 0 ? b_ary.push(k) : ary.push(k)}
        f_ary, b_ary = b_ary, []
        j *= i
      end
    }
    p ary
    
[/code]

出力結果  
[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]

（余談）  
Project euler において、素因数の最小値がらみの問題が日本時間2015/06/21(Sun) 09:00
に出題されました。（<https://projecteuler.net/problem=521>）

i の素因数の最小値を smpf(i) とし、  
2 ≦ i ≦ n の範囲における smpf(i) の和 (=S(n)) に関する問題です。


CC BY-SA 3.0
2015-05-21T10:57:56.837
10465
2015-07-09T20:06:16.807
2015-07-09T20:06:16.807
5363
5363
10436
answer


言い方を変えると、以下の3つのキーを、この優先順でソートする、ということになりますね。

  * 最小の素因数
  * その次数
  * 元の数

気付いたら Haskell で書いてました。  
C# で Linq 使うなどするともっと素直に書けそう。

[code]

    import Data.List (sort)
    
    -- x に含まれる因数 f の次数を求める。
    factorOrder :: (Integral a) => a -> a -> Int
    factorOrder x f = case divMod x f of
                        (y, 0) -> 1 + factorOrder y f
                        _      -> 0
    
    -- x の最小の素因数とその次数を求める。
    firstPrimaryFactor :: (Integral a) => a -> (a, Int)
    firstPrimaryFactor x = firstPrimaryFactorSub x 2
                           where
                             firstPrimaryFactorSub x f = case factorOrder x f of
                                                           0 -> firstPrimaryFactorSub x (f + 1)
                                                           n -> (f, n)
    
    -- 今回の問題に対応するソート。
    -- ((最小の素因数,その次数),元々の数) についてソートを行うことで実現。
    theSort :: (Integral a) => [a] -> [a]
    theSort = (map snd) . sort . (map (\x -> (firstPrimaryFactor x, x)))
    
    -- 100 まで。
    main :: IO ()
    main = print $ theSort [2..100]
    
[/code]

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


CC BY-SA 3.0
2015-05-22T03:55:07.893
10486
2015-05-22T04:59:07.950
2015-05-22T04:59:07.950
7831
7831
10436
answer


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

**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]

* * *

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


CC BY-SA 3.0
2015-05-22T05:05:09.357
10491
2015-05-22T13:28:57.730
2015-05-22T13:28:57.730
5300
5300
10436
answer