# Duncan's blog

## October 25, 2014

### Project Euler: problem 12 (PHP) – Highly divisible triangular number

Filed under: PHP,Project Euler — duncan @ 12:24 pm
Tags:

I’m doing these Project Euler mathematical puzzles as a simple practical exercise for teaching myself PHP, and I’d appreciate any feedback on my code.

Problem 12:

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …

Let us list the factors of the first seven triangle numbers:

1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

Here’s my code:

```<?php
\$limit = 500;
\$counter=1;

do {
\$currentTriangle = getTriangle(\$counter);

\$countFactors = getCountFactors(\$currentTriangle);

\$counter++;
} while (\$countFactors <= \$limit);

echo \$currentTriangle;

function getTriangle(\$number) {
return \$number * (\$number + 1) / 2;
}

function getCountFactors(\$number) {
\$countFactors = 0;
\$root = sqrt(\$number);

for (\$i = 1; \$i <= \$root; \$i++) {
if (\$number % \$i == 0) {
\$countFactors += 2;
}
}

return \$countFactors;
}

```

To begin with I was adding each factor into an array, returning that, then counting the length of the array.  However I later realised I didn’t really need to do that, I could just increment the count of factors by 2 each time.  Originally I was doing:

```	for (\$i = 1; \$i <= sqrt(\$number); \$i++) {
if (\$number % \$i == 0)
{
\$factors[] = \$i;
\$factors[] = \$number / \$i;
}
}```

Getting rid of that array didn’t really make any improvements on speed.  However, one other amendment did; in my for loop I was calculating the square root on every iteration of the loop:

`	for (\$i = 1; \$i <= sqrt(\$number); \$i++) {`

Moving that value into a variable prior to the for loop more than halved the execution time, from about 25 seconds(!) to about 11:

```	\$root = sqrt(\$number);

for (\$i = 1; \$i <= \$root; \$i++) {```