21xrx.com
2024-09-19 09:19:41 Thursday
登录
文章检索 我的文章 写文章
C++快速求约数的方法
2023-07-02 08:55:24 深夜i     --     --
C++ 约数 快速

在C++中,求一个数的约数是经常会遇到的问题,特别是在数学竞赛中。传统的方法是从1到n枚举每一个数字,然后判断它是否是n的约数。但是这样做的时间复杂度是O(n),对于大数而言会非常耗时。那么有没有一种更快速的方法呢?答案是肯定的,下面就介绍一种C++求约数的快速方法。

我们知道,一个数n的正因数总是成对出现的,比如n=12,它的正因数是1,2,3,4,6,12,可以看到1和12是一对,2和6是一对,3和4是一对。因此,我们只需要枚举1到根号n的范围内的数字,然后判断它是否是n的约数,如果是,则可以得到另一个约数,这样就可以一次性将两个约数都找到,从而大大减少了时间复杂度。

那么具体的实现方法是怎样的呢?可以参考下面的代码:


vector<int> get_divisors(int n) {

  vector<int> res;

  for (int i = 1; i <= sqrt(n); i++) {

    if (n % i == 0) {

      res.push_back(i);

      if (i != sqrt(n)) {

        res.push_back(n / i);

      }

    }

  }

  return res;

}

以上代码中,我们使用了vector来存储求得的约数,首先从1到根号n枚举每一个数字,然后判断它是否是n的约数,如果是则将其加入到vector中。如果这个数字不等于根号n,也就是它不是自身的因数,那么我们还需要将n除以这个数字得到的结果加入到vector中。

这种方法的时间复杂度是O(根号n),可以看到比传统枚举的时间复杂度要快得多。如果是在数学竞赛中遇到了求一个数的约数的问题,记得使用这种更快速的方法来解决。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复