c - 您在我提供的代码中选择一种代码而不是另一种代码的原因是什么？有什么建议可以改进它们吗？

Question

下面的程序计算能被 1 到 20 中所有数字整除的最小正数。您会在两者之间选择哪一个？为什么？ 第一段代码:

#include <stdio.h>

#define ulong unsigned long

int main(void)
{
const ulong val = 20;
ulong x;
ulong y;

for (x = val; ; x += val)
{
    for (y = val - 1; y; y--)
    {
        if (x % y != 0)
        {
            break;
        }
    }

    if (y == 0)
    {
        printf("Answer = %u \n", x);
        break;
    }
}
return 0;
}

第二段代码:

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

bool isDivisable(int x);

int main()
{
    int a = 20;
    while (true)
    {
        a+=20;
        if (isDivisable(a))
        {
            break;
        }
    }
    printf("%d\n", a);
    system("pause");
    return 0;
}

bool isDivisable(int x)
{
    for (int i = 11; i < 21; i++)
    {
        if (x%i != 0)return false;

    }
    return true;
}

另外，这个 for 循环代表什么？: 对于 (y = val - 1; y; y--) 它会迭代直到达到什么程度？代码 (y = val - 1; ; y--) 会产生相同的结果吗？

Answer 1

您要查找的号码是least common multiple (LCM)从1到20的所有数字。在这种情况下，LCM将等于数字素因数分解中每个素因数的最高幂的乘积。

因此，结果将等于2^4 * 3^2 * 5 * 7 * 11 * 13 * 17 * 19 = 232792560

如果你想找到从1到N所有数字的最小公倍数，你可以简单地使用sieve of Eratosthenes 查找从 1 到 N 的所有素数或选择任何更优化的算法。 C 语言示例(第一次重写代码):

#define ulong unsigned long

int main(void)
{
    const ulong val = 20;
    int isNotPrime[val+1];
    memset(isNotPrime, 0, sizeof(isNotPrime));

    isNotPrime[0] = isNotPrime[1] = 1;

    ulong res = 1;
    for (ulong i = 2; i <= val; ++i) {
        if (!isNotPrime[i]) {
            res *= pow(i, (int) (log(val) / log(i)));
        }

        for (ulong j = i*i; j <= val; j += i) {
            isNotPrime[j] = 1;
        }
    }
    printf("Answer = %lu \n", res);
    return 0;
}