Original

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 primes factors. What is the first of these numbers?

和訳

連続する2つの数がそれぞれ2つの異なる素因数を持つのは

14 = 2 × 7
15 = 3 × 5 の場合である.
同様に連続する3つの数がそれぞれ3つの異なる素因数を持つのは

644 = 22 × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19 の場合である.
連続する4つの数がそれぞれ4つの異なる素因数を持つ場合を考え, 連続する数の中で最小のものを答えよ.

当てにならないソースコード(C#)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
using System;
using System.Collections.Generic;

namespace ProjectEuler {
    class Problem47 : Problem{
        public Problem47() {
            Primes p = new Primes();
            List<long> numbers = new List<long>();
            for (long i = 2 * 3 * 5 * 7;; i++) {
                var f = p.PrimeFactors(i);
                if (f.Count != 4)
                    continue;
                numbers.Add(i);
                int n = numbers.Count - 1;
                if (n < 3)
                    continue;
                bool found = true;
                for (int j = 1; j < 4; j++) {
                    if(numbers[n-j] != i - j){
                        found = false;
                    }
                }
                if (found) {
                    Console.WriteLine("> " + (i-3));
                    break;
                }
            }
        }
    }
}


整数nを素因数分解
→素因数が4個ならリストに追加
→連続しているか調べる
を繰り返しています。
こういう答えの予測がつかない問題に配列は使いにくいため、
リストを使っているのですが、そのせいでだいぶ時間がかかっています。
(自分のマシンで数秒かかります)

Problem 46 Index Problem 48