10537


以前  
（[2からNまでを、素因数分解したときの素因数の最小値が小さい順に並べるには？](https://ja.stackoverflow.com/questions/10436/2%E3%81%8B%E3%82%89n%E3%81%BE%E3%81%A7%E3%82%92-%E7%B4%A0%E5%9B%A0%E6%95%B0%E5%88%86%E8%A7%A3%E3%81%97%E3%81%9F%E3%81%A8%E3%81%8D%E3%81%AE%E7%B4%A0%E5%9B%A0%E6%95%B0%E3%81%AE%E6%9C%80%E5%B0%8F%E5%80%A4%E3%81%8C%E5%B0%8F%E3%81%95%E3%81%84%E9%A0%86%E3%81%AB%E4%B8%A6%E3%81%B9%E3%82%8B%E3%81%AB%E3%81%AF)  
および  
[2からNまでを、素因数分解したときの次数によって並べるには？](https://ja.stackoverflow.com/questions/10472/2%E3%81%8B%E3%82%89n%E3%81%BE%E3%81%A7%E3%82%92-%E7%B4%A0%E5%9B%A0%E6%95%B0%E5%88%86%E8%A7%A3%E3%81%97%E3%81%9F%E3%81%A8%E3%81%8D%E3%81%AE%E6%AC%A1%E6%95%B0%E3%81%AB%E3%82%88%E3%81%A3%E3%81%A6%E4%B8%A6%E3%81%B9%E3%82%8B%E3%81%AB%E3%81%AF)）  
と異なる規則によって、2からNまでを並びかえを行います。

①2〜Nまでを素因数分解を行い次数のみ取り出しその和を求める。  
②次数の和が小さい順に並べる。次数の和が同じなら、元の数の大きさが小さい方が先とする。

例えば、N = 10 の場合、次のようになります。  
①  
2 => 1,  
3 => 1,  
4 => 2,  
5 => 1,  
6 => 2,  
7 => 1,  
8 => 3,  
9 => 2,  
10 => 2  
②  
2, 3, 5, 7, 4, 6, 9, 10, 8  
となる。

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

参考までに何の工夫もしていないコード（Ruby）を挙げておきます。

[code]

    require 'prime'
    
    N = 10
    h = {}
    (2..N).each{|i|
      s = 0
      i.prime_division.map{|j| s += j[1]}
      h.key?(s) ? h[s] = h[s].push(i) : h[s] = [i]
    }
    p h.values.flatten
    
[/code]

（追記）  
三回にわたって似たような質問をしたのは、  
以下のようなコードを見つけるためでした。  
これまでご回答いただいた方々へ厚く御礼申し上げます。

[code]

    require 'prime'
    
    N = 51
    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
    
[/code]

出力結果（検証用の出力は省く）  
[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]  
↑  
2〜51までを順番に出力したのではありません。


CC BY-SA 3.0
2015-05-22T10:49:03.470
10503
2015-05-23T14:24:51.787
2017-04-13T12:52:39.113
-1
5363
question
アルゴリズム
2からNまでを、素因数分解したときの次数の和の順に並べるには？


次数和を中心に考えて、

  * 次数和 = 1 で構築できる、 N 以下の合成数 (というか素数そのもの) のソート済リスト
  * 次数和 = 2 で構築できる、 N 以下の合成数のソート済リスト
  * 次数和 = 3 で...

と、得られるリストが空になるまで次数和を増やしていき、それらを結合するというのはどうでしょう。  
この方法は、ベタに素因数分解をしていく方法よりコードは煩雑になりますが、リストを得る際の除算が不要になります。  
とはいえ、素数リストを作るのに結局除算が必要になるので、本当に除算が減ってくれるか否かは微妙ですが。(未検証)

ruby はまともに書けないため、HaskellとC++で書いてみました。  
最初からソート済のリストを得る方法が思い付かなかったため、そこは素直にソートしています (C++ではちょっと小細工していますが)。

(ruby って、素数リストが標準で入ってるんだよね。羨しい……)

Haskell 版。

[code]

    import Data.List (sort)
    
    -- 素数の無限リスト。
    primes :: [Integer]
    primes = 2 :  filter (\x -> and $ map ((/= 0) . (mod x))
                                    $ takeWhile (\y -> y * y <= x) primes)
                         [3, 5 ..]
    
    -- 昇順リスト xs から重複を許して選んだ
    -- n 個の要素すべてと currの積がmaxを超えない
    -- ような積の全リスト。
    -- 関数名は、悩んだ挙句投げやりなものに。
    theProducts :: [Integer] -> Integer -> Integer -> Int -> [Integer]
    theProducts _      _   curr 0 = [curr]
    theProducts (x:xs) max curr n = if (x * curr) > max then []
                                    else theProducts (x:xs) max (x * curr) (n - 1)
                                         ++ theProducts xs max curr n
    
    -- max 以下で、次数合計が 1 のもの, 2 のもの... (それぞれソート済)
    -- を、空リストが返ってくるまで求め、それらを結合する
    -- ことで解とする。
    solve :: Integer -> [Integer]
    solve max = foldl1 (++) $ takeWhile (/= []) $ map (sort . theProducts primes max 1) [1..]
    
    main :: IO ()
    main = print $ solve 100
    
[/code]

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

C++ (C++11) 版。素数リストを有限リストにしただけで、ほぼHaskell版のベタ移植。そして長い……  
合成数を `std::set` に放り込むことで、最後にまとめてソートせずに済むようにしています。

[code]

    #include <iostream>
    #include <set>
    #include <vector>
    #include <list>
    #include <utility>
    #include <algorithm>
    #include <iterator>
    
    using num_t = int;
    
    // max 以下の素数のリストを得る。ただし2は必ず含まれる (手抜き)。
    std::list<num_t> get_primes(num_t max)
    {
        std::list<num_t> primes;
        for(num_t n = 3; n <= max; n += 2)
        {
            bool is_prime = true;
            for(auto p : primes)
            {
                if(p * p > max)
                {
                    break;
                }
                if(n % p == 0)
                {
                    is_prime = false;
                    break;
                }
            }
            if(is_prime)
            {
                primes.push_back(n);
            }
        }
        primes.push_front(2);
        return std::move(primes);
    }
    
    
    // 昇順リスト [first, last) から重複を許して
    // 選んだ n 個の要素すべてと curr の積が max を
    // 超えないような積の集合を得る。
    void get_list_products(
        std::set<num_t> &products,
        std::list<num_t>::const_iterator first,
        std::list<num_t>::const_iterator last,
        num_t max, num_t curr, int n)
    {
        if(n <= 0)
        {
            products.insert(curr);
            return;
        }
    
        if((first == last) || (curr * *first > max))
        {
            return;
        }
    
        get_list_products(products, first, last, max, curr * *first, n - 1);
        get_list_products(products, ++first, last, max, curr, n);
    }
    
    
    int main()
    {
        const num_t N = 100;
        std::vector<num_t> result;
    
        const auto primes = get_primes(N);
    
        for(int n = 1; ; n++)
        {
            std::set<num_t> products;
            get_list_products(products, primes.begin(), primes.end(), N, 1, n);
            if(products.empty())
            {
                break;
            }
    
            std::copy(products.begin(), products.end(), std::back_inserter(result));
        }
    
        for(auto x : result)
        {
            std::cout << x << ", ";
        }
        std::cout << std::endl;
    
        return 0;
    }
    
[/code]

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


CC BY-SA 3.0
2015-05-22T16:55:13.217
10523
2015-05-22T16:55:13.217
7831
10503
answer


(別に大した方法じゃないですが) 素因数分解なし・ソートなしの方法

  * 素因数分解はしたくないので、逆に合成する方針です
  * 合成は @yoh2 さんと同様に次数和ごとに行いますが、1つ小さい次数和の結果を再利用します
  * 別の配列 `degrees[2～N]` に生成した数の次数和を記録して、  
最後にそれを読み出すことでソートを免れます

  * 時間計算量のオーダーは O(N) です(…多分)

※素数列の生成は、"Atkin の篩 [[参考URL](http://d.hatena.ne.jp/uwitenpen/20111203) by
@Manyama さん][実装例: [Spaghetti
Source](http://www.prefield.com/algorithm/math/sieve_of_atkin.html)]"
を用いれば時間計算量 O(N/log log N) らしいので、全体としてもこの方針で O(N) な物を作れるはずです。残念ながら、Ruby の Prime
は、エラトステネスの篩 (～O(N log log N)) の様ですが。

**Ruby コード** :

[code]

    #!/usr/bin/env ruby
    require 'prime'
    include Math
    
    def factorization_degree_ordered_sequence(n)
      maxDegree = log(n, 2).round
      degrees = Array.new(n + 1)
    
      # degrees[合成数]=次数和 の表を作る
      primes = Prime.each(n).to_a
      composites = [[1,0]] # [[合成数, 最大素因数], ...], 次数和0について初期化
      (1 .. maxDegree).each{|degree| # 次数和昇順ループ
        composites = composites.flat_map{|(u, i)|
          (i .. primes.length - 1).lazy
            .map{|j| [u * primes[j], j]}
            .take_while{|(v, j)| v <= n && ( degrees[v] = degree )}.force
        }
      }
    
      # 合成数を次数和毎に振り分けてから連結
      ret = Array.new(maxDegree + 1) { [] }
      (2 .. n).each{|i| ret[degrees[i]] << i}
      ret.flatten
    end
    
    p factorization_degree_ordered_sequence(10)
    p factorization_degree_ordered_sequence(100)
    
[/code]

**説明** :  
(※面倒なので、素数や 1 も便宜上合成数に含めて呼んでしまいますが気にしないで下さい…)

先ず、「合成数 → 次数和」 のテーブル `degrees[合成数]` を作ります:
基本は次数和についてのループで、素因数を掛けていく事により合成数を生成しつつ `degrees[合成数]=次数和`
をして行きます。テーブルさえ完成すれば、後は (質問文のコードと同様に) 次数和ごとに振り分けてから配列をくっつければ良いです。

合成数を生成する部分について、もう少し説明しておきます。

  * 配列 `primes` は使う可能性のある素因数たちです。
  * 配列 `composites` は現在の次数和(degree)における `[合成数, 最大素因数の番号]` たちを含みます。但し、`最大素因数の番号` は配列 `primes` におけるインデックスです。
  * 初期の `composites` は、便宜的に、次数和 0 として 合成数 = 1, 最大素因数番号 = 0 を登録しておきます: `composites = [[1, 0]]`。
  * 或る次数和の `composites` は、1つ下の次数和の合成数に素因数を1つかける事で生成します。ただし、重複して生成されないように「新しくかける素因数は現在の最大素因数以上」という制限をかけます。

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

* * *

おまけ

**愚直な実装(Ruby)** 素因数分解 × ソート (テスト用):

[code]

    #!/usr/bin/env ruby
    require 'prime'
    
    def factorization_degree_ordered_sequence(n)
      (2 .. n).sort_by{|v| [v.prime_division.map{|f| f[1]}.reduce(:+), v]}
    end
    
    p factorization_degree_ordered_sequence(10)
    
[/code]

**重複組合せ(Ruby)** `repeated_combination` を使ってみる × ソート:

[code]

    #!/usr/bin/env ruby
    require 'prime'
    
    def factorization_degree_ordered_sequence(n)
      primes = Prime.each(n).to_a
      (1 .. log(n, 2)).flat_map{|degree|
        limit = n / 2 ** (degree - 1)
        primes
          .select{|factor| factor <= limit}
          .repeated_combination(degree)
          .map{|factors| factors.reduce(:*)}
          .select{|value| value <= n }
          .sort
      }
    end
    
    p factorization_degree_ordered_sequence(10)
    
[/code]

**C++版** (比較用):

[code]

    #include <cstdlib>
    #include <cstdint>
    #include <cmath>
    #include <utility>
    #include <iterator>
    #include <vector>
    #include <iostream>
    
    typedef std::int64_t value_type;
    
    // エラトステネスの篩
    //   実はこれなら割り算なしで素数列が作れる。但しメモリは食う。
    template<typename OutputIterator>
    void sieve_of_eratosthenes(OutputIterator output, value_type n) {
      std::vector<value_type> mark(n + 1, 0);
      value_type i = 2, imax = std::round(std::sqrt(n));
      for(; i <= imax; i++){
        if(mark[i])continue;
        *output++ = i;
        for(value_type j = i * 2; j <= n; j += i)
          mark[j] = 1;
      }
      for(; i <= n; i++)
        if(!mark[i])
          *output++ = i;
    }
    
    // 目的の数列を生成
    template<typename OutputIterator>
    void factorization_degree_ordered_sequence(OutputIterator output, value_type n) {
      int const maxDegree = std::round(std::log2(n));
      std::vector<value_type> degrees(n + 1, 0);
    
      // degrees[合成数]=次数和
      std::vector<value_type> primes;
      sieve_of_eratosthenes(std::back_inserter(primes), n);
      std::vector<std::pair<value_type, int> > composites = { std::make_pair(1, 0) }, composites2;
      for(int degree = 1; degree <= maxDegree; degree++) {
        composites2.clear();
    
        for(auto const& pair : composites){
          for(int j = pair.second; j < primes.size(); j++) {
            value_type const v = pair.first * primes[j];
            if(v > n)break;
            composites2.push_back(std::make_pair(v, j));
            degrees[v] = degree;
          }
        }
    
        composites.swap(composites2);
      }
    
      // 次数和で振り分け・連結
      std::vector<std::vector<value_type> > ret(maxDegree + 1);
      for(value_type i = 2; i <= n; i++)
        ret[degrees[i]].push_back(i);
      for(auto const& ret_ : ret)
        for(auto const& value : ret_)
          *output++ = value;
    }
    
    int main(int argc, char** argv) {
      value_type const n = 1 < argc ? std::atoi(argv[1]) : 10;
    
      std::vector<value_type> buff;
      buff.reserve(n);
    
      factorization_degree_ordered_sequence(std::back_inserter(buff), n);
      for(auto const& value : buff)
        std::cout << value << ", ";
      std::cout << std::endl;
    
      return 0;
    }
    
[/code]

* * *

編集: C++ コード追記しました。  
編集: @Manyama さん御紹介の "Atkin の篩 参考URL" を追記しました。


CC BY-SA 3.0
2015-05-23T09:21:04.043
10537
2015-05-23T14:24:51.787
2015-05-23T14:24:51.787
5300
5300
10503
answer