RubyでProject Euler - Problem 35

Problem 35 (Project Euler) [原文]

197は巡回素数と呼ばれる. 桁を回転させたときに得られる数 197, 971, 719 が全て素数だからである.

100未満には巡回素数が13個ある: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, および97である. 100万未満の巡回素数は何個か?

素数のうちの一桁でも偶数や"5"があると、桁を循環させるうちに合成数になるので、これをスキップすることが考えられます。

でも、この条件分岐は私のコードではあまり速度向上につながらない一方、見た目が汚かったので書き入れませんでした。

また、素数をそのまま配列で持つよりも「エラストテネスの篩(sieve)」を示すブール配列とするほうがすっきりします。

  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


  $primes = prime_sieve(99_9999)

  def is_circular?(prime) # 循環素数か否か
    str = prime.to_s
    (str.length-1).times do |i|
      return false unless $primes[str.concat(str.slice!(0, 1)).to_i]
    end
    true
  end

  cnt = 0
  $primes.each_with_index do |v, i|
    next unless v
    cnt += 1 if i < 10 || is_circular?(i)
  end

  puts cnt

ご注意

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

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

コメントはありません。

ご注意

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