読者です 読者をやめる 読者になる 読者になる

Project Euler 47

Problem 47

using System;
using System.Collections.Generic;

class PE47 {
    // count distinct prime factors
    static int CountDistinctPrimes(int n) {
        var primeSet = new HashSet<int>();

        while (n % 2 == 0) {
            primeSet.Add(2);
            n /= 2;
        }

        for (int i = 3; i*i <= n; i += 2) {
            while (n % i == 0) {
                primeSet.Add(i);
                n /= i;
            }
        }

        if (n > 1) primeSet.Add(n);
        return primeSet.Count;
    }

    static void Main() {
        for (int i = 3; /* */; i++) {
            if (4 == CountDistinctPrimes(i)) {
                bool valid = true;
                for (int j = 1; j <= 3; j++) {
                    if (4 != CountDistinctPrimes(i + j)) {
                        valid = false;
                        break;
                    }
                }

                if (valid) {
                    Console.WriteLine(i);
                    break;
                }
            }
        }
    }
}