判断一个整数是否为丑数的C++实现 |21xrx.com

判断一个整数是否为丑数的C++实现

2023-07-05 03:30:43 深夜i -- --

整数判断丑数 C++ 实现

丑数是指只包含因子2、3和5的正整数，例如6、8都是丑数，而14不是丑数。下面是一个C++实现，判断一个整数是否为丑数。


bool isUgly(int num) {
  if(num == 0)
    return false;
  
  while(num%2 == 0)
    num /= 2;
  
  while(num%3 == 0)
    num /= 3;
  
  while(num%5 == 0)
    num /= 5;
  
  return num == 1;
}

首先判断数是否为0，若为0，则不是丑数。接着去除因子2、3、5，直至不能再除为止，最后判断剩余的数是否为1，若是则为丑数，否则不是。

该算法的时间复杂度为$O(logn)$，因为每不断去除因子2、3、5后，剩余的数会越来越小，去除的次数不会超过logn。

上一篇: idea打包java可执行jar包

下一篇: C++程序员如何寻找最大值？

评论区

()

相似文章

C++判断一个数是否是丑数

C++是一种十分强大的编程语言，用它编写代码可以非常高效和简便。在C++中，我们可以通过一些简单的方法来判断一个数是否是丑数。