Problem 58: Spiral Primes

gistfile1.txt

# http://projecteuler.net/problem=58
# this is the same spiral from http://projecteuler.net/problem=28

# doing individual prime tests is faster than using a seive for numbers this large
def is_prime(n):
  if n == 2 or n == 3: return True
  if n < 2 or n%2 == 0: return False
  if n < 9: return True
  if n%3 == 0: return False
  r = int(n**.5)
  f = 5
  while f <= r:
    if n%f == 0: return False
    if n%(f+2) == 0: return False
    f +=6
  return True	

# i just adjusted the p28 code to count primes on each ring			
total = 1
term = 2 
prime_count = 0 
total_diagonal_count = 0
ratio = 1.0
j=1
while ratio > .10:
	start = total + 1
	a = start + (term-1)
	b = a + term
	c = b + term
	d = c + term
	if is_prime(a) == True: prime_count += 1.0
	if is_prime(b) == True: prime_count += 1.0
	if is_prime(c) == True: prime_count += 1.0
	if is_prime(d) == True: prime_count += 1.0
	total_diagonal_count += 4.0
	ratio = prime_count/total_diagonal_count
	if ratio <= 0.10:
		print j, "ratio is less than 10%", 1+2*j,"sided box"
	total = d
	term +=2
	j=j+1