RubyでProject Euler - Problem 47

Problem 47 (Project Euler) [原文]

連続する2つの数がそれぞれ2つの異なる素因数を持つのは

• 14 = 2 × 7
• 15 = 3 × 5

の場合である.

同様に連続する3つの数がそれぞれ3つの異なる素因数を持つのは

• 644 = 2² × 7 × 23
• 645 = 3 × 5 × 43
• 646 = 2 × 17 × 19

の場合である.

連続する4つの数がそれぞれ4つの異なる素因数を持つ場合を考え, 連続する数の中で最小のものを答えよ.

豪勢な合成数が４つ連続するほど、「素数日照り」の数域はどこらあたりかはちょっと知りたいところです。

素因数分解は素早く処理したいところです。でも、647を起点にして5分近くかかってしまいました。もうちょっとチューニングするべきかな。

出来が悪いけど、この際、コードを追記に貼ります。

  def prime_sieve(upper) # エラストテネスの篩
    sieve = Array.new(upper + 1,true)
    sieve[0] = sieve[1] = false
    2.upto(Math.sqrt(upper)) do |i|
      next unless sieve[i]
      (i + i).step(upper,i){ |j| sieve[j] = false }
    end
    sieve
  end

  def prime_list(upper) # エラストテネスの篩から素数だけを抽出した配列作成
    return [] if upper < 2
    primes=Array.new
    prime_sieve(upper).each_with_index{ |isPrime,i| primes.push i if isPrime }
    primes
  end

  def get_factors_num(num) # numの素因数の種類数をカウント
    factors = Hash.new # キーで素因数種を記録
    $p_list.each do |v|
      if num % v == 0
        num /= v
        factors[v] = true # 値に意味はない
        break if v > num
        redo
      end
    end
    factors.length # ハッシュのサイズを返す
  end

  limit = 100_0000
  $p_list = prime_list(limit)

  n = 647 # 問題文より
  seq = Array.new(0)
  flag = true # whileループ脱出用フラグ
  while flag
    printf("= %d\r", n) # モニタ
    (0..3).each do |i|
      if get_factors_num(n+i) != 4
        n += i + 1 # iの分を加算
        flag = true
        break
      else
        flag = false
      end
    end
  end

  printf("\n** %d\n", n)

ご注意

当分の間、トラックバックの受信を行わないことといたしました。過去に戴いたトラックバックのリストについてはそのまま保持いたします。

トラックバックはありません

コメントはありません。

ご注意

当分の間、JavaScript が有効でないとコメント投稿できないようにします。スパム対策であって、投稿される方の個人情報を取得する目的ではありません。悪しからずご了承ください。