読者です 読者をやめる 読者になる 読者になる

mu chance or much chance ?

日々の戯れ言

Project Euler 51

Project Euler

Problem51を解きました.

  • Prime digit replacements

By replacing the 1st digit of the 2-digit number *3, it turns out that six of the nine possible values: 13, 23, 43, 53, 73, and 83, are all prime.

By replacing the 3rd and 4th digits of 56**3 with the same digit, this 5-digit number is the first example having seven primes among the ten generated numbers, yielding the family: 56003, 56113, 56333, 56443, 56663, 56773, and 56993. Consequently 56003, being the first member of this family, is the smallest prime with this property.

Find the smallest prime which, by replacing part of the number (not necessarily adjacent digits) with the same digit, is part of an eight prime value family.

https://projecteuler.net/problem=51

問題は「桁を同じ数で置き換えることで,8つの素数が得られる最小の素数を求めよ.」.

require 'prime'

Prime.each do |pNum|
  numStr = '1234567890'
  numArray = pNum.to_s.split('')
  if numArray.count('0') >= 2
    count = 0
    numStr.length.times do |i|
      temp = Marshal.load(Marshal.dump(numArray))
      temp.length.times do |j|
        temp[j] = numStr[i] if temp[j] == '0'
      end
      count += 1 if Prime.prime?(temp.join.to_i) && temp.join.to_i.to_s.length == numArray.length
    end
    if count == 8
      p numArray.join.to_i
      break
    end
  end

  if numArray.count('1') >= 2
    count = 0
    numStr.length.times do |i|
      temp = Marshal.load(Marshal.dump(numArray))
      temp.length.times do |j|
        temp[j] = numStr[i] if temp[j] == '1'
      end
      count += 1 if Prime.prime?(temp.join.to_i) && temp.join.to_i.to_s.length == numArray.length
    end
    if count == 8
      p numArray.join.to_i
      break
    end
  end

  next unless numArray.count('2') >= 2
  count = 0
  numStr.length.times do |i|
    temp = Marshal.load(Marshal.dump(numArray))
    temp.length.times do |j|
      temp[j] = numStr[i] if temp[j] == '2'
    end
    count += 1 if Prime.prime?(temp.join.to_i) && temp.join.to_i.to_s.length == numArray.length
  end
  if count == 8
    p numArray.join.to_i
    break
  end
end

思ったより簡単で助かりました.

1つの数字を変えるだけでは,
mod3の観点から8つの素数を得ることはできないので,
2つ以上の数字を変えることになります.

また,最小の数を求める必要があるので,
注目すべき数字は「0」「1」「2」の3種類になります.

詰まったところは,数字を変えたときに,
上位桁が0になる場合の対処が抜けていて,
結果を得ることができなかったところです.