检查一个数字是否被许多其他人均分

Question

我有一个编程问题,希望我检查30,000个六角形数字(由公式:H(n)= n(2n-1)给出),其中有多少可以被数字1到12整除.

我的代码如下:

#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;
}

现在我知道我现在在if语句中的检查是非常低效的,所以我想知道是否有更简单的方法来检查数字？我尝试使用for循环,但无法使其工作(假设它一次只检查1个数字).有任何想法吗？

Answer 1

如果a[i] | x是的话1 <= i <= n,那么lcm(a[1], ..., a[n]) | x

对于这种情况,只需要检查是否lcm(1,2,...,12) | h,即h % 27720 == 0

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