The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.
There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.
How many circular primes are there below one million?
require "prime"
p Prime.each(1_000_000).select{|p|
a = p.to_s.split('').map(&:to_i)
b = a.dup
is = true
loop do
b.push(b.shift)
break if b == a
unless b.join.to_i.prime?
is = false
break
end
end
is
}.size
[code=ruby]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 = 2*i
while j <= n
sito[j] = nil
j += i
end
end
i += 2
end
return [2] + (3…n).select do |i|
i if sito[i] == true && i.odd?
end
end
class Array
def rotation
return (1…self.size).map {|r|
self.slice(r-1,self.size)+self.slice(0,r-1)
}
end
end
list = [2,5]+eratostenes(1_000_000).select{|prime| !(prime.to_s =~ /[0,2,4,5,6,8]/) }
puts list.select{|p| p.to_s.split(’’).to_a.rotation.map{|t| t.join.to_i}.all?{|e| list.index(e)}}.size[/code]
Jaką wersje ruby trzeba mieć by korzystać z klasy Prime?
Korzystałem z klasy Prime, ale z mathn:
require 'mathn'
list = []
Prime.new.each do |prime|
break if prime > n
list << prime unless prime.to_s =~ /[0,2,4,5,6,8]/
end
ale była dużo wolniejsza od sita eratostenesa
prime jest w ruby 1.9
% ruby1.9 --version
ruby 1.9.0 (2008-06-20 revision 17482) [i486-linux]
% irb1.9
irb(main):001:0> require 'prime'
LoadError: no such file to load -- prime
from (irb):1:in `require'
from (irb):1
from /usr/bin/irbb:12:in `<main>'
update:
dzięki, poszukam nowszych paczek
[teamon ~/Dropbox/euler] ruby1.9 --version
ruby 1.9.1p0 (2009-01-30 revision 21907) [i386-darwin9.6.0]
[teamon ~/Dropbox/euler] irb1.9
irb(main):001:0> require 'prime'
=> true