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

mu chance or much chance ?

日々の戯れ言

Project Euler 47

Project Euler

Problem47を解きました.

  • Distinct primes factors

The first two consecutive numbers to have two distinct prime factors are:

14 = 2 × 7
15 = 3 × 5

The first three consecutive numbers to have three distinct prime factors are:

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

Find the first four consecutive integers to have four distinct prime factors. What is the first of these numbers?

https://projecteuler.net/problem=47

問題は「最初に現れるそれぞれ4つの異なる素因数を持つ連続する4つの数の最初の数を求めよ.」.

require 'prime'

i = 2
k = 4
loop do
  div1 = []
  div2 = []
  div3 = []
  factors1 = Prime.prime_division(i)
  if factors1.length != k
    i += 1
    next
  end
  factors2 = Prime.prime_division(i + 1)
  if factors2.length != k
    i += 1
    next
  end
  factors3 = Prime.prime_division(i + 2)
  if factors3.length != k
    i += 1
    next
  end
  factors4 = Prime.prime_division(i + 3)
  if factors4.length != k
    i += 1
    next
  end

  for j in 0..k - 1 do
    div1.push(factors1[j][0])
    div1.push(factors2[j][0])
    div2.push(factors2[j][0])
    div2.push(factors3[j][0])
    div3.push(factors3[j][0])
    div3.push(factors4[j][0])
  end

  div1.sort!.uniq!
  div2.sort!.uniq!
  div3.sort!.uniq!

  unless div1.length == k * 2 && div2.length == k * 2 && div3.length == k * 2
    i += 1
    next
  end
  p i
  break
end

力技で解きました.ソースコードが少し汚いです.