Problem58.py

import math

pd = 0
nd = 1

def layer(n):
	global pd, nd
	n += 1
	side = n * 2 - 1
	count = side * 2 + (side - 2) * 2
	start = (side - 2)**2 + 1
	step = side - 1
	for x in xrange(step - 1, count, step):
		i = start + x
		assert x & 1
		prime = True
		top = int(math.sqrt(i))
		prime = top * top != i
		if prime:
			for j in xrange(3, top, 2):
				if i % j == 0:
					prime = False
					break
		if prime:
			pd += 1
		else:
			nd += 1

	return pd, nd, float(pd) / (pd + nd), side

i = 1
while True:
	_, _, ratio, side = layer(i)
	if ratio < 0.1:
		print side
		break
	i += 1