Project Euler Problem 47

Problem 47

04 July 2003

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?

Answer: 134043

 

C#

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;

namespace Euler {
    static class Program {
        static HashSet<int> primeFactors(int num) {
            var r = new HashSet<int>();
            var n = num;
            for (var pf = 2; pf * pf <= num; pf++) {
                if (n % pf == 0) {
                    r.Add(pf);
                    n /= pf;
                    while (n % pf == 0) n /= pf;
                }
            }
            if (n > 1) r.Add(n);
            return r;
        }

        static void Main(string[] args) {
            var factors = new Dictionary<int, HashSet<int>>();
            for (var i = 2; i < 1000000000; i++) {
                var pfs = primeFactors(i);
                if (pfs.Count == 4) {
                    if (factors.Count >= 4) factors.Remove(factors.Keys.Min());
                    factors.Add(i, pfs);
                    if (factors.Count >= 4 && factors.Keys.Max() - factors.Keys.Min() == 3) {
                        foreach (var fkv in factors) {
                            Console.Write(fkv.Key + ": ");
                            foreach (var f in fkv.Value)
                                Console.Write(f + " ");
                            Console.WriteLine();
                        }
                        break;
                    }
                }
            }
            Console.ReadKey();
        }
    }
}