Project Euler > Problem 147 > Rectangles in cross-hatched grids (Java Solution)

Problem:

In a 3x2 cross-hatched grid, a total of 37 different rectangles could be situated within that grid as indicated in the sketch.

There are 5 grids smaller than 3x2, vertical and horizontal dimensions being important, i.e. 1x1, 2x1, 3x1, 1x2 and 2x2. If each of them is cross-hatched, the following number of different rectangles could be situated within those smaller grids:

1x1: 1
2x1: 4
3x1: 8
1x2: 4
2x2: 18

Adding those to the 37 of the 3x2 grid, a total of 72 different rectangles could be situated within 3x2 and smaller grids.

How many different rectangles could be situated within 47x43 and smaller grids?

Solution:

134043

Code:
The solution may include methods that will be found here: Library.java .

public interface EulerSolution{

public String run();

}

/* 
 * Solution to Project Euler problem 47
 * By Nayuki Minase
 * 
 * http://nayuki.eigenstate.org/page/project-euler-solutions
 * https://github.com/nayuki/Project-Euler-solutions
 */


public final class p047 implements EulerSolution {
	
	public static void main(String[] args) {
		System.out.println(new p047().run());
	}
	
	
	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 = Library.sqrt(n); i <= end; i++) {
			if (n % i == 0) {
				do n /= i;
				while (n % i == 0);
				count++;
				end = Library.sqrt(n);
			}
		}
		if (n > 1)
			count++;
		return count;
	}
	
}