Euler Project Problem #035

euler35.rb

# Solution to Project Euler's thirty-fifth problem
# http://projecteuler.net/index.php?section=problems&id=35
# How many circular primes are there below one million?

# This program needs a substantial rewrite. All Euler Project problems should take less than one minute to run, this one runs in 39 minutes.

def generate_primes(ceiling)
	primes, count = [1, 2], 1
	until primes.last > ceiling do
		numbers = (primes[count-1]**2+1..primes[count]**2).to_a
		1.upto(count) {|c| numbers.select! {|number| number%primes[c] != 0}}
		primes.concat(numbers)
		count += 1
	end
	primes.shift # remove 1
	until primes.last <= ceiling do primes.pop end # remove too high primes.
	return primes
end
def first_to_last(number)
	number = number.to_s
	number << number.slice!(0)
	return number.to_i
end
def circular_prime?(prime, primes, circ_primes)
	bool = false
	prime.to_s.length.times do 
		if circ_primes.include?(prime) then
			return bool # skip it if it was already put into the array.
		else
			prime = first_to_last(prime)
			unless primes.include?(prime) then
				return bool
			end
		end
	end
	bool = true
	return bool
end
a = Time.new
ceiling = 99
primes = generate_primes(ceiling)
circular_primes = []
## primes.keep_if do |prime| # reduce set of primes tested to those whose tens or greater digits are odd.
p primes
primes.each do |prime|
	if circular_prime?(prime, primes, circular_primes) then
		prime.to_s.length.times do 
			prime = first_to_last(prime)
			circular_primes.push prime
		end
	end
end
p circular_primes.uniq!
p circular_primes.length
b = Time.new - a
p b