Project Euler Problem 50
問題
The prime 41, can be written as the sum of six consecutive primes: 41 = 2 + 3 + 5 + 7 + 11 + 13 This is the longest sum of consecutive primes that adds to a prime below one-hundred. The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953. Which prime, below one-million, can be written as the sum of the most consecutive primes?
ソース
max = 1000000 prime = Array.new(max, 1) prime[0..1] = [0, 0] i = 2 while i < Math.sqrt(max).to_i + 1 do (i + i).step(max, i){|x| prime[x] = 0} i += prime[(i + 1)..max].index(1) + 1 end len = 0 ans = 0 array = prime.each_index{|i| prime[i] = i unless prime[i].zero? }.select{|x| !x.zero? } array.each_index{|i| count = 0 array[i...array.size].inject(0) {|s, x| s += x break if s >= max count += 1 ans, len = s, [len, count].max if !prime[s].zero? && len < count s } } puts ans
解答
997651
感想
O(N^2)となるので、かなり時間のかかりそうな計算に思えたが、以外に数秒で終わった。
Project Euler Problem 49
問題
The arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another. There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence. What 12-digit number do you form by concatenating the three terms in this sequence?
ソース
max = 10000 prime = Array.new(max, 1) prime[0..1] = [0, 0] i = 2 while i < Math.sqrt(max).to_i + 1 do (i + i).step(max, i){|x| prime[x] = 0} i += prime[(i + 1)..max].index(1) + 1 end prime.each_index{|i| prime[i] = i unless prime[i].zero? }.select{|x| !x.zero? && x >= 1000}.each{|x| array = x.to_s.scan(/./).permutation(4).map{|a| a.join.to_i}.uniq.sort.select{|y| y >= 1000 && !prime[y].zero? } next if array[0] != x next if array.size < 3 array.each_index{|i| (1..(array.size - i - 2)).each{|a| add = array[i + a] - array[i] if array.find{|y| y == array[i] + add} && array.find{|y| y == array[i] + add + add} puts "#{array[i]}#{array[i] + add}#{array[i] + add + add}" break end } } }
解答
296962999629
感想
実はこれ、少しハマりました。。。
ソース汚い
とりあえず解けて満足です
Project Euler Problem 48
問題
The series, 1^1 + 2^2 + 3^3 + ... + 10^10 = 10405071317. Find the last ten digits of the series, 1^1 + 2^2 + 3^3 + ... + 1000^1000.
ソース
puts (1..1000).inject(0){|s, i| s + i**i} % (10 ** 10)
解答
9110846700
感想
ここまで来て１行プログラムとは、Rubyすごすぎです！
Project Euler Problem 47
問題
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^2 × 7 × 23 645 = 3 × 5 × 43 646 = 2 × 17 × 19. Find the first four consecutive integers to have four distinct primes factors. What is the first of these numbers?
ソース
require 'mathn' n = 4 pd = (1...1 + n).map{|i| i.prime_division} (1 + n).upto(10 ** 6){|i| pd.shift pd << i.prime_division all = pd.inject([]){|a, x| a + x} if pd.all?{|x| x.size == n} && all.size == all.uniq.size puts i - n + 1 break end }
解答
134043
感想
全ての[素因数, 乗数]の組を配列として、uniqすると全てが異なる素因数かが判断できます。
これもそんなに難しくない
Project Euler Problem 46
問題
It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square. 9 = 7 + 2×1^2 15 = 7 + 2×2^2 21 = 3 + 2×3^2 25 = 7 + 2×3^2 27 = 19 + 2×2^2 33 = 31 + 2×1^2 It turns out that the conjecture was false. What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?
ソース
require 'mathn' max = 10000 $prime = Array.new(max, 1) $prime[0..1] = [0, 0] i = 2 while i < Math.sqrt(max).to_i + 1 do (i + i).step(max, i){|x| $prime[x] = 0} i += $prime[(i + 1)..max].index(1) + 1 end prime_array = $prime.each_index{|i| $prime[i] = i unless $prime[i].zero? }.select{|x| !x.zero?} class Integer def composite? pd = self.prime_division return false unless pd.inject(0){|s, x| s + x[1]} >= 2 pd.all?{|x| !$prime[x[0]].zero? } end end 3.step(prime_array.last, 2){|i| next if !i.composite? if prime_array.select{|x| x <= i}.find{|x| (i - x) / 2 == Math.sqrt((i - x) / 2).floor ** 2}.nil? puts i break end }
解答
5777
感想
PCが無い時代だったら5777まで現れなかったら、このような予想が出てくるのも無理がない！
これも、問題通り実装するだけで解けるかな！
Project Euler Problem 45
問題
Triangle, pentagonal, and hexagonal numbers are generated by the following formulae: Triangle T(n)=n(n+1)/2 1, 3, 6, 10, 15, ... Pentagonal P(n)=n(3n−1)/2 1, 5, 12, 22, 35, ... Hexagonal H(n)=n(2n−1) 1, 6, 15, 28, 45, ... It can be verified that T(285) = P(165) = H(143) = 40755. Find the next triangle number that is also pentagonal and hexagonal.
ソース
t, ti = 1, 1 e, ei = 1, 1 h, hi = 1, 1 while true min = [t, e, h].min t, ti = ti * (ti + 1) / 2, ti +1 if min == t e, ei = ei * (ei * 3 - 1) / 2, ei + 1 if min == e h, hi = hi * (hi * 2 - 1), hi + 1 if min == h break if t == e && e == h && t > 40755 end puts t
解答
1533776805
感想
かなり大きい数字だけど、一瞬で答えが出ます。
結構これ以上無いというアルゴリズムだと思いますw
