Project euler #58
27 Dicembre 2012
Starting with 1 and spiralling anticlockwise in the following way, a square spiral with side length 7 is formed. 37 36 35 34 33 32 31 38 17 16 15 14 13 30 39 18 5 4 3 12 29 40 19 6 1 2 11 28 41 20 7 8 9 10 27 42 21 22 23 24 25 26 43 44 45 46 47 48 49 It is interesting to note that the odd squares lie along the bottom right diagonal, but what is more interesting is that 8 out of the 13 numbers lying along both diagonals are prime; that is, a ratio of 8/13 ~ 62%. If one complete new layer is wrapped around the spiral above, a square spiral with side length 9 will be formed. If this process is continued, what is the side length of the square spiral for which the ratio of primes along both diagonals first falls below 10%?
python:
import time ts = time.time() _MEMO = {3:3, 5:5, 7:8} def is_prime(num): if num <= 1: return False elif num == 2: return True elif num % 2 == 0: return False else: d = 3 r = int(num**0.5) while d <= r: if num % d == 0: return False d += 2 return True def get_spiral_primes(side): count = 0 for i in xrange(1,4): if is_prime(side**2 - i*side + i): count += 1 return count def spiral(side): _MEMO[side] = _MEMO[side-2] + get_spiral_primes(side) return _MEMO[side] for i in xrange(7, 1000000, 2): if spiral(i)/float(i * 2 - 1) < 0.1: break print "PE58: %s\nelapsed time: %ssec" %(i, time.time() - ts)
Categorie:Project Euler, python
Commenti recenti