# Project Euler problem 12: highly divisible triangular number

I am just a beginner in C++ and I tried solving this problem:

What is the first number of the form 1 + 2 + 3 + … + n that has over five hundred factors?

But it seems my code is not that efficient because its taking ages to find the answer:

#include<iostream>
using namespace std;

void triNum(int);

int main()
{
int res=0;
for (int i=1;i<100000000;i++){
res+=i;
triNum(res);
}
cout<<endl;
}

void triNum(int n)
{
int counter=0;
for(int i=1;i<=n;i++){
if(n%i==0){
counter+=1;
}
}
if(counter==500){
cout<<n;
}
}


The program is slow for several reasons:

1. The triNum function finds all the divisors. It doesn't need to. After you find 500 divisors, you could print the number and return from the function

• The function doesn't do what the problem description asked: it prints a number only when it has exactly 500 divisors, but the problem asks for the first number with over 500 divisors. If the first number has 502 divisors that would be a valid answer but your program will never print that.
2. Even after finding a number with over 500 divisors, your program would continue running until it checks 100000000 numbers. That's completely unnecessary, it should exit after finding the first appropriate number.

3. The program doesn't reuse the counts it already calculated. For example, after counting the divisors of 100, that could be reused when counting the divisors of 200. You could greatly benefit from using a map to cache already calculated counts.

The program has several other violations of good practices:

• using namespace std is considered bad practice
• The expression int i=1;i<100000000;i++ is too compact, it's recommended to put spaces around operators and after semicolons, like this: int i = 1; i < 100000000; i++
• triNum is a poor name: it fails to describe what the function does
• 100000000 and 500 are magic numbers. It would be better to put these values in constants with descriptive names

You're solving the wrong problem. The challenge is to find the first triangular number with over 500 divisors. Your code looks for the first triangular number with exactly 500 divisors.

Your code has both good parts, and parts that need improving on. Lets start with the good points

1) Good indentation, it is consistent and properly aligned

2) It has a good layout

3) Calculating the next triangle number is done in constant time, this is good because it saves a bunch of time, you aren't adding 1 to n every time you want the next one.

And the bits that need attention

1) void triNum(int);

This isn't really needed, if you move the method triNum above the main method, it does the same thing, and then you don't have to worry about if you change the return type or the parameter type.

2) More spaces, it makes it easier to find what you are looking for, and half the page isn't being used.

3) Don't shorten variable names, if you can thing of a name like result, use that instead of res, then in a few months you wont be guessing what it is short for, and you wont have to comment it

Finally, onto the code,

for (int i=1;i<100000000;i++)


We don't know when the first number is going to be, it could be after 1000, or it could be after 1000000000000, so we can't really put a number here, we could be way off, lets replace it with a boolean which we should set to true for (int i = 1; notFound; i++)

Next we call the triNum method, which is doing a lot of work. We could instead of checking the number of factors inside of it, return it and let another method deal with the specifics

int factors = triNum(n);


So that means we can remove the check inside of the method

int triNum(int n) //we have to change the method header, so it returns ints
{
int counter=0;
for(int i=1;i<=n;i++){
if(n%i==0){
counter+=1;
}
}

return counter;
}


While we are here, lets make this a bit faster, if we find out that some number a divides n, for example 3 divides 24, then we also know that n/a divides n, 24/3 = 8, and 8 divides 24, so whenever we find a number, we can increase the counter by 2. This also means we can stop checking before the square root of n, because any number bigger than the sqrt has a partner below it, and we already would have found it. This leaves us with only checking up to sqrt(n) rather than up to n, so it is a lot faster.

We have one special case, if we tried this for say 16, we would miss 4 as a factor, so we should put in a check to see if the the sqrt divides n. If it does, we found one more factor

int numberOfFactors(int n) //we can also change the method to have a name that better reflects what it does
{
int root = (int) sqrt(n); //don't forget to import math.h for the sqrt function
int counter=0;
for(int i = 1; i < root; i++){
if(n % i == 0){
counter += 2;
}
}
if(n % root == 0) counter += 1;
return counter;
}


lastly, we should update the main method so that it prints out the first triangle number with more factors than 500

int main()
{
int res=0;
int desiredNumber = 500;
bool notFound = true;
for (int i = 1; notFound; i++){
res+=i;
int factors = numberOfFactors(res);
if(factors > desiredNumber) notFound = false;
}
cout<<res<<endl;
}


And done, and it should take a lot less time