4

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

0

4 件の回答 4

3

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

Ruby コード:

#!/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)

説明:

最小素因数とその次数が (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]


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

1

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

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]
2
  • N が70 の場合の出力結果が、 [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, 19, 49, 5, 35, 65, 31, 59, 7, 11, 55, 13, 17, 23, 25, 29, 37, 41, 43, 47, 53, 61, 67] となったのですが、27より後の順番が違っている気がします。
    – TOM
    Commented 2015年5月21日 13:04
  • ご指摘ありがとうございます。lから要素削除してしまうのでs = l[::p]ではダメでした。修正しました。
    – yohjp
    Commented 2015年5月21日 13:36
1

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

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

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

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]

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

0

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

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

出力結果
[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)) に関する問題です。

1
  • 1
    回答記入欄で、コードの前に 改行 <!-- language: lang-ruby --> 改行 を入れると Ruby の文法で色付けがされますよ (質問にタグ ruby が入っていれば何も指定しなくても Ruby で色付けしてくれる訳ですが、一般の言語を対象とした質問では自分で言語を指定するとよいです…)。
    – akinomyoga
    Commented 2015年5月23日 4:20

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。