Solution to 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?

• Java Code

package sikademy;
/**
 *
 * @author Archangel Macsika
 * Copyright (c) Sikademy. All rights reserved
 */

public class SikademyEulerSolution {
	
	public String run() {
		for (int i = 2; ; i++) {
			if (       has4PrimeFactors(i + 0)
			        && has4PrimeFactors(i + 1)
			        && has4PrimeFactors(i + 2)
			        && has4PrimeFactors(i + 3))
				return Integer.toString(i);
		}
	}
	
	
	private static boolean has4PrimeFactors(int n) {
		return countDistinctPrimeFactors(n) == 4;
	}
	
	
	private static int countDistinctPrimeFactors(int n) {
		int count = 0;
		for (int i = 2, end = sqrt(n); i <= end; i++) {
			if (n % i == 0) {
				do n /= i;
				while (n % i == 0);
				count++;
				end = sqrt(n);
			}
		}
		if (n > 1)
			count++;
		return count;
	}

	public static int sqrt(int x) {
		if (x < 0)
			throw new IllegalArgumentException("Square root of negative number");
		int y = 0;
		for (int i = 1 << 15; i != 0; i >>>= 1) {
			y |= i;
			if (y > 46340 || y * y > x)
				y ^= i;
		}
		return y;
	}


	public static void main(String[] args) {
                SikademyEulerSolution solution = new SikademyEulerSolution();
		System.out.println(solution.run());
	}	
}

• Python Code

# 
# @author Archangel Macsika
# Copyright (c) Sikademy. All rights reserved.
# 

import itertools


def compute():
	cond = lambda i: all((count_distinct_prime_factors(i + j) == 4) for j in range(4))
	ans = next(filter(cond, itertools.count()))
	return str(ans)


def sqrt(x):
	assert x >= 0
	i = 1
	while i * i <= x:
		i *= 2
	y = 0
	while i > 0:
		if (y + i)**2 <= x:
			y += i
		i //= 2
	return y


# The underlying function must take only positional arguments, no keyword arguments.
class memoize:

	def __init__(self, func):
		self.func = func
		self.cache = {}

	def __call__(self, *args):
		if args in self.cache:
			return self.cache[args]
		else:
			val = self.func(*args)
			self.cache[args] = val
			return val

@memoize
def count_distinct_prime_factors(n):
	count = 0
	while n > 1:
		count += 1
		for i in range(2, sqrt(n) + 1):
			if n % i == 0:
				while True:
					n //= i
					if n % i != 0:
						break
				break
		else:
			break  # n is prime
	return count


if __name__ == "__main__":
	print(compute())