ホーム - Project Euler

Problem 47¶

Distinct Primes Factors¶

The first two consecutive numbers to have two distinct prime factors are:

\begin{align} 14 &= 2 \times 7\\ 15 &= 3 \times 5. \end{align}

The first three consecutive numbers to have three distinct prime factors are:

\begin{align} 644 &= 2^2 \times 7 \times 23\\ 645 &= 3 \times 5 \times 43\\ 646 &= 2 \times 17 \times 19. \end{align}

Find the first four consecutive integers to have four distinct prime factors each. What is the first of these numbers?

異なる素因数¶

それぞれ2つの異なる素因数を持つ連続する2つの数が最初に現れるのは:

\begin{align} 14 &= 2 \times 7\\ 15 &= 3 \times 5. \end{align}

それぞれ3つの異なる素因数を持つ連続する3つの数が最初に現れるのは:

\begin{align} 644 &= 2^2 \times 7 \times 23\\ 645 &= 3 \times 5 \times 43\\ 646 &= 2 \times 17 \times 19. \end{align}

最初に現れるそれぞれ4つの異なる素因数を持つ連続する4つの数を求めよ. その最初の数はいくつか?

(import (scheme base)
        (gauche base))

(define (factorize num)
  "異なる素因数を列挙する"
  (assume (exact-integer? num))
  (assume (<= 2 num))
  (let loop ([index 2] [rest num] [lis '()])
    (cond
      [(= rest 1) lis]
      [(< num (* index index))
       (cons rest lis)]
      [(and (zero? (mod rest index))
            (not (null? lis))
            (= index (car lis)))
       (loop index
             (div rest index)
             lis)]
      [(zero? (mod rest index))
       (loop index
             (div rest index)
             (cons index lis))]
      [else
        (loop (+ index 1) rest lis)])))

(define first-4factorize-sequence
  (let loop ([n1 645])
    (let ([n2 (+ n1 1)]
          [n3 (+ n1 2)]
          [n4 (+ n1 3)])
      (if (and (<= 4 (length (factorize n1)))
               (<= 4 (length (factorize n2)))
               (<= 4 (length (factorize n3)))
               (<= 4 (length (factorize n4))))
        (cons* n1 n2 n3 n4 '())
        (loop (+ n1 1))))))

(define answer-47
  (car first-4factorize-sequence))

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