ホーム - 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.

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の渦巻きが形成される.

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

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

(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)