Project Euler Problem 35

問題

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?

ソース

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

class Integer
	def circular_prime?
		n = self
		n.to_s.size.times {
			return false if $prime[n].zero?
			n = n / 10 + n % 10 * (10 ** (n.to_s.size - 1))
		}
		true
	end
end

puts $prime.each_index{|i|
	$prime[i] = i unless $prime[i].zero?
}.select{|x| !x.zero?}.select{|x|
	x.circular_prime?
}.size

解答

55

感想

循環素数かどうかの判定メソッドを作ってしまえば、あとはカウントするのみ！
循環は計算によって実現しています。