主页 / 问题 / 1565761
Accepted
user23328595
Asked:2024-02-11 07:58:44 +0000 UTC2024-02-11 07:58:44 +0000 UTC

给定一个自然数，检查这个自然数是否可以通过三个素数的乘积计算出来

  • 772

有一个问题，我想不出解决方案，我什至不知道，或者更确切地说，我有一个想法，如何做一个埃拉托色尼筛子，将所有数字输入到一个数组中，但是那么我需要如何正确地相乘呢？据我了解，它将是 2 3 5，它们相乘，不适合，然后它将是 2 3 7、2 3 11，依此类推，直到数组末尾，然后它将是类似的3 2 5, 3 5 7, 3 5 11，然后是 5 2 3, 5 3 7, 5 7 11 等等，但是行不行，行的话怎么写，我不求代码，只是文字上的解决方案，或者如果我的想法是正确的，我对此表示怀疑，那么还有一个记录选项，提前致谢

c++

1 个回答

  1. Best Answer

    对于小范围（例如，在 内int），您可以简单地使用暴力，甚至无需构建素数表。简单因式分解 - 分解为素数并在分解过程中直接计算数量。就像是

    bool isTriple(unsigned int N)
{
    int cnt = 0;
    while (N%2 == 0) { N/=2; cnt++;}
    if (cnt > 3) return false;
    for(int i = 3; i < sqrt(N) + 1; i+=2)
    {
        if (N%i == 0) while(N%i == 0) { N/=i; cnt++;}
        if (cnt > 3) return false;
    }
    if (N > 1) cnt++;
    return cnt == 3;
}
    • 0

相关问题