Project Euler

[ホーム](https://redmine.noppi.jp) - [[Wiki|Project Euler]]

# [[Problem 58]]

## Spiral Primes

Starting with $1$ and spiralling anticlockwise in the following way, a square spiral with side length $7$ is formed.

|  |  |  |  |  |  |  |

|--|--|--|--|--|--|--|

| <span style="color:red">**37**</span> | 36 | 35 | 34 | 33 | 32 | <span style="color:red">**31**</span> |

| 38 | <span style="color:red">**17**</span> | 16 | 15 | 14 | <span style="color:red">**13**</span> | 30 |

| 39 | 18 | <span style="color:red">**5**</span> | 4 | <span style="color:red">**3**</span> | 12 | 29 |

| 40 | 19 | 6 | 1 | 2 | 11 | 28 |

| 41 | 20 | <span style="color:red">**7**</span> | 8 | 9 | 10 | 27 |

| 42 | 21 | 22 | 23 | 24 | 25 | 26 |

| <span style="color:red">**43**</span> | 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 \approx 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\%$?

## 螺旋素数

1から始めて, 以下のように反時計回りに数字を並べていくと, 辺の長さが7の渦巻きが形成される.

|  |  |  |  |  |  |  |

|--|--|--|--|--|--|--|

| <span style="color:red">**37**</span> | 36 | 35 | 34 | 33 | 32 | <span style="color:red">**31**</span> |

| 38 | <span style="color:red">**17**</span> | 16 | 15 | 14 | <span style="color:red">**13**</span> | 30 |

| 39 | 18 | <span style="color:red">**5**</span> | 4 | <span style="color:red">**3**</span> | 12 | 29 |

| 40 | 19 | 6 | 1 | 2 | 11 | 28 |

| 41 | 20 | <span style="color:red">**7**</span> | 8 | 9 | 10 | 27 |

| 42 | 21 | 22 | 23 | 24 | 25 | 26 |

| <span style="color:red">**43**</span> | 44 | 45 | 46 | 47 | 48 | 49 |

面白いことに, 奇平方数が右下の対角線上に出現する. もっと面白いことには, 対角線上の13個の数字のうち, 8個が素数である. ここで割合は$8/13 \approx 62$ %である.

渦巻きに新しい層を付け加えよう. すると辺の長さが9の渦巻きが出来る. 以下, この操作を繰り返していく. 対角線上の素数の割合が10%未満に落ちる最初の辺の長さを求めよ.

```scheme

(import (scheme base)

        (gauche base))

(define (prime? num)

  (assume (exact-integer? num))

  (assume (positive? num))

  (cond

    [(= num 1) #f]

    [(= num 2) #t]

    [(even? num) #f]

    [(= num 3) #t]

    [(zero? (mod num 3)) #f]

    [else

      (let loop ([n6-1 5])

        (let ([n6+1 (+ n6-1 2)])

          (cond

            [(< num

                (* n6-1 n6-1))

             #t]

            [(zero? (mod num n6-1))

             #f]

            [(< num

                (* n6+1 n6+1))

             #t]

            [(zero? (mod num n6+1))

             #f]

            [else

              (loop (+ n6+1 4))])))]))

(define edge-p

  (let loop ([edge 3]

             [init 3]

             [all 1]

             [prime-count 0]

             [result '()])

    (let* ([inc (- edge 1)]

           [n1 init]

           [n2 (+ n1 inc)]

           [n3 (+ n2 inc)]

           [n4 (+ n3 inc)]

           [next-all (+ all 4)]

           [next-prime-count prime-count])

      (when (prime? n1)

        (set! next-prime-count (+ next-prime-count 1)))

      (when (prime? n2)

        (set! next-prime-count (+ next-prime-count 1)))

      (when (prime? n3)

        (set! next-prime-count (+ next-prime-count 1)))

      (when (prime? n4)

        (set! next-prime-count (+ next-prime-count 1)))

      (let ([p (/ (* next-prime-count 100.0)

                  next-all)])

        (if (< p 10)

          (reverse (cons `(,edge . ,p) result))

          (loop (+ edge 2)

                (+ n4 edge 1)

                next-all

                next-prime-count

                (cons `(,edge . ,p) result)))))))

(define answer-58

  (car (last edge-p)))

(format #t "58: ~d~%" answer-58)

```