Skip to main content
問題文を紹介するのはまずいかもしれないので、削除した。
ソース リンク
TOM
  • 1,582
  • 1
  • 14
  • 37

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の和 (=S(n) としたとき、
S(10^12) mod 10^9 を求めよ
というに関する問題です
面白い問題なので、挑戦してみてはいかがでしょうか

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) としたとき、
S(10^12) mod 10^9 を求めよ
という問題です
面白い問題なので、挑戦してみてはいかがでしょうか

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)) に関する問題です。

問題文修正。
ソース リンク
TOM
  • 1,582
  • 1
  • 14
  • 37

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) としたとき、
S(10^12) mod 10^9 を求めよ
という問題です。
面白い問題なので、挑戦してみてはいかがでしょうか。

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) としたとき、
S(10^12) mod 10^9 を求めよ
という問題です。
面白い問題なので、挑戦してみてはいかがでしょうか。

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) としたとき、
S(10^12) mod 10^9 を求めよ
という問題です。
面白い問題なので、挑戦してみてはいかがでしょうか。

余談を追加。
ソース リンク
TOM
  • 1,582
  • 1
  • 14
  • 37

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) としたとき、
S(10^12) mod 10^9 を求めよ
という問題です。
面白い問題なので、挑戦してみてはいかがでしょうか。

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]

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) としたとき、
S(10^12) mod 10^9 を求めよ
という問題です。
面白い問題なので、挑戦してみてはいかがでしょうか。

myogoさんのコメントより
ソース リンク
TOM
  • 1,582
  • 1
  • 14
  • 37
読み込んでいます
既出チェックは配列でなくても良かったので、修正。
ソース リンク
TOM
  • 1,582
  • 1
  • 14
  • 37
読み込んでいます
[編集が猶予期間中に取り消されました]
ソース リンク
TOM
  • 1,582
  • 1
  • 14
  • 37
読み込んでいます
パラメータの変更。
ソース リンク
TOM
  • 1,582
  • 1
  • 14
  • 37
読み込んでいます
ソース リンク
TOM
  • 1,582
  • 1
  • 14
  • 37
読み込んでいます