Project Euler – Highly divisible triangular number (Part 2)

I managed to improve my algorithm…down to 1 second.

Let’s see what I did using the triangular number 28 from the problem description.

screenshot_87.png

divisors = [].

i = 1.
28 % 1 == 0 → true.
k = 28 / 1 = 28.
divisors.contains(1) → false, add 1 to divisors.
divisors.contains(28) → false, add 28 to divisors as well.
Therefore divisors = [1, 28].

Continue with i = 2.
28 % 2 == 0 → true.
k = 28 / 2 = 14.
divisors.contains(2) → false,
add 2 to divisors.
divisors.contains(14) → false,
add 14 to divisors.
divisors = [1, 2, 14, 28].

And so on…

28 % 3 == 0 → falsedivisors = [1, 2, 14, 28].
28 % 4 == 0 → true, divisors = [1, 2, 4, 7, 14, 28].
28 % 5 == 0 → false,  divisors = [1, 2, 4, 7, 14, 28].
28 % 6 == 0 → false,  divisors = [1, 2, 4, 7, 14, 28].

…until…

28 % 7 == 0 → true
divisors.contains(7) → true.

Break and done!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s