Problem 37

Projekt Euler w Ruby
1

Problem 37

The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.

Find the sum of the only eleven primes that are both truncatable from left to right and right to left.

NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.

2

[code=ruby]require ‘mathn’

def eratostenes(n)
sito = Array.new(n, true)
sito[0],sito[1],sito[2] = nil,nil,true
i = 3
while i <= n do
unless sito[i]==nil then
j = 2i
while j <= n
sito[j] = nil
j += i
end
end
i += 2
end
return [2] + (3…n).select{|i| sito[i] == true && i.odd?}
end
class Integer
def truncatable?
return false if self.to_s.length < 2 || ( self.to_s.length > 2 && self.to_s =~ ( /^[0,1,2,4,5,6,8][:digit:][0,1,2,4,5,6,8]$/ ) )
return (1…self.to_s.length).map do |n|
[self.to_s.slice(n-1,self.to_s.length).to_i, self.to_s.slice(0,n).to_i]
end.flatten.all? {|prime| [2,3,5,7].index(prime) || $sieve.index(prime)}
end
end
$sieve = eratostenes(1_000_000).slice(4,1_000_000)

list = []
$sieve.each do |prime|
break if list.size >= 11
print “#{prime}\r”
if prime.truncatable?
list << prime
puts list.last
end
end

puts list.inject(:+)[/code]

3

Mam coś mniejszego:

[code=ruby]#!/usr/bin/env ruby
N = 1000000-1

$sieve = Array.new(N+1, true)
2.upto(N) { |n| (n*2).step(N, n) { |i| $sieve[i] = false if $sieve[n] } }
$sieve[0], $sieve[1] = false, false
$primes = [2]
3.step(N, 2) { |i| $primes << i if $sieve[i] }

def truncatable?(n)
if n >= 10
(1…n.to_s.size).all? do |i|
$sieve[n.to_s[i…-1].to_i] && $sieve[n.to_s[0…i-1].to_i]
end
else
false
end
end

i = 0
sum = 0
$primes.each do |n|
break unless i < 11
if truncatable?(n)
sum += n
i += 1
end
end
puts “sum=#{sum}, count=#{i}”[/code]

4

[code=ruby]require “prime”

class Fixnum
def rly_prime?
self != 0 && self != 1 && prime?
end
end

P = Prime.each
found = []

while found.size < 11
prime = P.next
next if prime < 8

left to right

a = prime
a /= 10 while a.rly_prime?

if a == 0
# right to left
b = prime
b = b % 10**(b.to_s.size-1) while b.rly_prime?
found << prime if b == 0
end
end
p found
p found.inject(:+)[/code]

5 
require 'prime'

class Fixnum
  alias :old_prime? :prime?
  def prime?
    self != 0 and self != 1 and self.old_prime?
  end
  
  def is_truncatable_prime?
    k = self
    loop do
      k = k % (10**(k.to_s.size-1))
      break if k == 0
      return false unless k.prime?
    end
    k = self
    loop do
      k = k / 10
      break if k == 0
      return false unless k.prime?
    end
    return true
  end
end

primes = Prime.each
t = []

loop do
  n = primes.next
  next if n < 10
  t << n if n.is_truncatable_prime?
  break t if t.size == 11
end

p t
p t.inject(:+)

Wyniki:

real 0m5.200s user 0m2.564s sys 0m0.008s
BTW. Może mi ktoś powiedzieć dlaczego standardowe prime? dla 0 i 1 zwraca true?