Project Euler [Problem 47]

素因数分解ね

問題

Distinct primes factors

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

14 = 2 × 7 15 = 3 × 5

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

644 = 2² × 7 × 23 645 = 3 × 5 × 43 646 = 2 × 17 × 19.

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

私訳

相異なる素因数

連続する二つの自然数で、いずれも相異なる二つの素因数を持つ最初の組は以下である。

14 = 2 × 7 15 = 3 × 5

連続する三つの自然数で、いずれも相異なる三つの素因数を持つ最初の組は以下である。

644 = 2² × 7 × 23 645 = 3 × 5 × 43 646 = 2 × 17 × 19.

連続する四つの自然数で、いずれも相異なる四つの素因数を持つ最初の組を探せ。その最初の数は何か？

解答方針

素因数分解を行って、数えるだけである。

素因数分解を素早く行いたいので、以下のようなデータ構造を作る。 factor : 長さ n + 1の整数の配列で、factor[i] には素数なら 1, そうでなければ最小の素因数が格納されている。 便宜的に、factor[0] = factor[1] = 1 としておく。 長さ 21 なら、 [1, 1, 1, 1, 2, 1, 2, 1, 2, 3, 2, 1, 2, 1, 2, 3, 2, 1, 2, 1, 2] という感じ。i は factor[i] で割り切れるので、割った商を見ればさらにその商が取れる。