|
| 1 | +""" |
| 2 | +Project Euler Problem 58:https://projecteuler.net/problem=58 |
| 3 | +
|
| 4 | +
|
| 5 | +Starting with 1 and spiralling anticlockwise in the following way, |
| 6 | +a square spiral with side length 7 is formed. |
| 7 | +
|
| 8 | +37 36 35 34 33 32 31 |
| 9 | +38 17 16 15 14 13 30 |
| 10 | +39 18 5 4 3 12 29 |
| 11 | +40 19 6 1 2 11 28 |
| 12 | +41 20 7 8 9 10 27 |
| 13 | +42 21 22 23 24 25 26 |
| 14 | +43 44 45 46 47 48 49 |
| 15 | +
|
| 16 | +It is interesting to note that the odd squares lie along the bottom right |
| 17 | +diagonal ,but what is more interesting is that 8 out of the 13 numbers |
| 18 | +lying along both diagonals are prime; that is, a ratio of 8/13 ≈ 62%. |
| 19 | +
|
| 20 | +If one complete new layer is wrapped around the spiral above, |
| 21 | +a square spiral with side length 9 will be formed. |
| 22 | +If this process is continued, |
| 23 | +what is the side length of the square spiral for which |
| 24 | +the ratio of primes along both diagonals first falls below 10%? |
| 25 | +
|
| 26 | +Solution: We have to find an odd length side for which square falls below |
| 27 | +10%. With every layer we add 4 elements are being added to the diagonals |
| 28 | +,lets say we have a square spiral of odd length with side length j, |
| 29 | +then if we move from j to j+2, we are adding j*j+j+1,j*j+2*(j+1),j*j+3*(j+1) |
| 30 | +j*j+4*(j+1). Out of these 4 only the first three can become prime |
| 31 | +because last one reduces to (j+2)*(j+2). |
| 32 | +So we check individually each one of these before incrementing our |
| 33 | +count of current primes. |
| 34 | +
|
| 35 | +""" |
| 36 | + |
| 37 | + |
| 38 | +def isprime(d: int) -> int: |
| 39 | + """ |
| 40 | + returns whether the given digit is prime or not |
| 41 | + >>> isprime(1) |
| 42 | + 0 |
| 43 | + >>> isprime(17) |
| 44 | + 1 |
| 45 | + >>> isprime(10000) |
| 46 | + 0 |
| 47 | + """ |
| 48 | + if d == 1: |
| 49 | + return 0 |
| 50 | + |
| 51 | + i = 2 |
| 52 | + while i * i <= d: |
| 53 | + if d % i == 0: |
| 54 | + return 0 |
| 55 | + i = i + 1 |
| 56 | + return 1 |
| 57 | + |
| 58 | + |
| 59 | +def solution(ratio: float = 0.1) -> int: |
| 60 | + """ |
| 61 | + returns the side length of the square spiral of odd length greater |
| 62 | + than 1 for which the ratio of primes along both diagonals |
| 63 | + first falls below the given ratio. |
| 64 | + >>> solution(.5) |
| 65 | + 11 |
| 66 | + >>> solution(.2) |
| 67 | + 309 |
| 68 | + >>> solution(.111) |
| 69 | + 11317 |
| 70 | + """ |
| 71 | + |
| 72 | + j = 3 |
| 73 | + primes = 3 |
| 74 | + |
| 75 | + while primes / (2 * j - 1) >= ratio: |
| 76 | + for i in range(j * j + j + 1, (j + 2) * (j + 2), j + 1): |
| 77 | + primes = primes + isprime(i) |
| 78 | + |
| 79 | + j = j + 2 |
| 80 | + return j |
| 81 | + |
| 82 | + |
| 83 | +if __name__ == "__main__": |
| 84 | + import doctest |
| 85 | + |
| 86 | + doctest.testmod() |
0 commit comments