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

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 .

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;

}

}

## No comments :

## Post a Comment