Project Euler Problem 47 Solution

Question

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

\begin{aligned} 14 & = 2 \times 7 \\ 15 & = 3 \times 5 \end{aligned}

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

\begin{aligned} 644 & = 2^2 \times 7 \times 23 \\ 645 & = 3 \times 5 \times 43 \\ 646 & = 2 \times 17 \times 19 \end{aligned}

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

Haskell

import Data.List (nub)

primes :: [Int]
primes = 2 : sieve primes [3,5..] where
    sieve (p:ps) xs = h ++ sieve ps [x | x <- t, rem x p /= 0]
                      where (h, t) = span (< p*p) xs

factorize :: Int -> [Int]
factorize n = primeFactors n primes where
    primeFactors 1 _ = []
    primeFactors _ [] = []
    primeFactors m (p:ps) | m < p * p = [m]
                          | r == 0 = p : primeFactors q (p:ps)
                          | otherwise = primeFactors m ps
                          where (q, r) = quotRem m p

uniqueFactors :: Int -> Int
uniqueFactors = length . nub . factorize

chunks :: Int -> [a] -> [[a]]
chunks n l | length chunk < n = []
           | otherwise = chunk : chunks n (tail l)
           where chunk = take n l

candidates :: [[Int]]
candidates = [cons | cons <- chunks 4 [1..], all ((== 4) . uniqueFactors) cons]

main :: IO ()
main = print $ head $ head candidates

$ ghc -O2 -o consecutive-factors consecutive-factors.hs
$ time ./consecutive-factors
real   0m0.076s
user   0m0.075s
sys    0m0.000s

Python

#!/usr/bin/env python
import math

def factorize(n):
    if n < 1:
        raise ValueError('fact() argument should be >= 1')
    if n == 1:
        return []  # special case
    res = []
    # iterate over all even numbers first.
    while n % 2 == 0:
        res.append(2)
        n //= 2
    # try odd numbers up to sqrt(n)
    limit = math.sqrt(n+1)
    i = 3
    while i <= limit:
        if n % i == 0:
            res.append(i)
            n //= i
            limit = math.sqrt(n+i)
        else:
            i += 2
    if n != 1:
        res.append(n)
    return res

def distinct_prime_factors(n):
    return set(factorize(n))

def main():
    chain = []
    search = 4
    for n in range(1, 1000000):
        if len(distinct_prime_factors(n)) == search:
            chain.append(n)
    print(next(chain[i:i+search] for i, n in enumerate(chain) if chain[i:i+search] == list(range(n, n+search)))[0])

if __name__ == "__main__": main()

$ time python3 consecutive-factors.py
real   0m12.762s
user   0m12.738s
sys    0m0.024s

Ruby

#!/usr/bin/env ruby
require 'mathn'
puts (1..1000000).each_cons(4).detect { |nums| 
  nums.all? { |n| n.prime_division.length == 4 } 
}[0]

$ time ruby consecutive-factors.rb
real   0m1.430s
user   0m1.430s
sys    0m0.000s