Checking if a number divides evenly by many others

Question

I have a programming problem that wants me to check of the 30,000 Hexagonal numbers (given by the formula: H(n) = n(2n-1) ), how many of them are divisible by the numbers 1 through 12.

I have code as follows:

#include <iostream>
#include <cstring>

using namespace std;

int main()
{
    int hex, count = 0;

    for (int n = 1; n <= 30000; n++)
    {
        hex = n * ((2 * n) - 1);

        if (hex % 1 == 0 && hex % 2 == 0 && hex % 3 == 0 && hex % 4 == 0 && hex % 5 == 0 && hex % 6 == 0 && hex % 7 == 0 && hex % 8 == 0 && hex % 9 == 0 && hex % 10 == 0 && hex % 11 == 0 && hex % 12 == 0)
        {
            count++;
        }
    }

    cout << count << endl;
}

Now I know the check I have right now in my if statement is very inefficient, so I was wondering if there was a simpler way to check the number? I tried using a for loop but couldn't get it to work (given it only checks 1 number at a time). Any ideas?

Answer 1

If a[i] | x for 1 <= i <= n, then lcm(a[1], ..., a[n]) | x

For this case, just need to check if lcm(1,2,...,12) | h, i.e. h % 27720 == 0

---

1. https://en.wikipedia.org/wiki/Least_common_multiple