CODEWITHSUNDEEP
c++if-statementfor-loopprogram-entry-pointiostream
Gardenia
Gardenia

Reputation: 41

Checking if a number divides evenly by many others

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?

Upvotes: 0

Views: 1778

Answers (2)

Tharindu Kumara
Tharindu Kumara

Reputation: 4458

You can simply use another for loop to get rid from the long if statement that you have used. 

#include <iostream>
#include <cstring>

using namespace std;

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

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

        int subcount = 0;
        for (int i = 1; i <= divider; ++i){
            if (hex % i == 0){
                ++subcount;
                if(subcount == devider){
                     ++count;
                }
            }
        }
    }

    cout << count << endl;
}

Upvotes: 1

delta
delta

Reputation: 3818

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

Upvotes: 8

Related Questions