Project Euler

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

# [[Problem 47]]

## Distinct Primes Factors

<p>The first two consecutive numbers to have two distinct prime factors are:</p>

\begin{align}

14 &= 2 \times 7\\

15 &= 3 \times 5.

\end{align}

<p>The first three consecutive numbers to have three distinct prime factors are:</p>

\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?

## 異なる素因数

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

\begin{align}

14 &= 2 \times 7\\

15 &= 3 \times 5.

\end{align}

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

\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つの数を求めよ. その最初の数はいくつか?

```scheme

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

```