## 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?

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;	}	}