#!/usr/bin/env ruby
# Solution to Project Euler problem 58
# Author: David J. Oftedal.
$isprime = Hash.new(false)
class Integer
# Determine if self is prime.
def prime?
return true if $isprime[self]
return true if self == 2 || self == 3
# Fast mini-primality test
return false if (self-1) % 6 != 0 && (self+1) % 6 != 0
return false if self < 2
# Slow, but deterministic primality test
# If self is divisible by any smaller prime, it's not prime.
# Try 2 and 3, plus all possible primes 6n±1 up to and including the square root.
return false if self%2 == 0 || self%3 == 0
(6..(self**0.5).to_i + 1).step(6).each {|f| return false if (self % (f-1) == 0 || self % (f+1) == 0)}
$isprime[self] = true
true
end
end
# Calculate the corners of an n*n square spiral starting from 1.
def diagonals
corner4 = 1 # Last number in the current row.
diff = 0 # Difference between each corner and the next.
size = 1
loop do
# The last number on each row is the square of the size.
corner4 = size*size
corner3 = corner4 - diff
corner2 = corner3 - diff
corner1 = corner2 - diff
# The difference between the corners increases by 2 in each row.
diff += 2
yield size, corner1, corner2, corner3, corner4
# Each row is 2 longer than the previous one.
size += 2
end
end
if $0 == __FILE__
# Find the dimension of the smallest spiral in which the ratio of primes
# to non-primes in the diagonals is below 10%.
primes = 0.0
nonprimes = 0.0
diagonals do |size, a, b, c, d|
if size == 1
nonprimes += 1.0
else
[a, b, c, d].each {|n| n.prime? ? primes += 1.0 : nonprimes += 1.0}
end
if primes/(primes+nonprimes) < 0.1 && size > 1
puts "The ratio of primes in the diagonals first falls below 10% in the spiral of size " << size.to_s << "x" << size.to_s << "."
break
end
end
end