Wednesday, August 25, 2010

Project Euler : How many circular primes are there below one million?

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?


Solution (in Ruby)

The solution to this problem invovles one performance enhancement in finding the prime numbers. If you want to check whether the same number is prime more than once in your program, it is highly important to have a look on the running time. That is why I am using an array to store the number as the index itself. This would make sure that the number given is found to be prime or not in O(1) time. Rest of the solution did what the problem statement demands

def find_prime(n)
  return false if n <= 1
  2.upto(Math.sqrt(n).to_i) do |x|
    return false if n%x == 0
  end
  true
end
large = []
1.upto(1000000) { |each_num| large[each_num] = true if find_prime(each_num) }
count = 0
1.upto(1000000) do |num|
  str = num.to_s
  all = (0...str.length).collect { |i| large[((str * 2)[i, str.length]).to_i] ? true : false }
  count+=1 if all.inject(0){|b,i| b&&=i}
end
puts "The count of such primes is #{count}"

Hover here to see the solution

Cheers!!
Bragaadeesh

No comments: