检查一个数是否能被许多其他数整除

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

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

Answer 2

您可以简单地使用另一个 for 循环来摆脱您使用过的长 if 语句。

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

检查一个数是否能被许多其他数整除

Checking if a number divides evenly by many others

c++

iostream

main

for-loop

if-statement