LeetCode.每日一题 2427. 公因子的数目

 

Halo，这里是Ppeua。平时主要更新C语言，C++，数据结构算法......感兴趣就关注我吧！你定不会失望。

🌈个人主页：主页链接

🌈算法专栏：专栏链接

     我会一直往里填充内容哒！

🌈LeetCode专栏：专栏链接 

    目前在刷初级算法的LeetBook 。若每日一题当中有力所能及的题目，也会当天做完发出

🌈代码仓库：Gitee链接

🌈点击关注=收获更多优质内容🌈

目录

题目:公因子的数目

题解:

代码实现:

 公约数的个数与公约数之和:

完结撒花：

 

题目:公因子的数目

题解:

是一题简单题，我们借此来复习下数论里的求最大公约数。

先给出一种解法:暴力枚举

将一个数的所有约数枚举出来,存入数组,之后再用数组中的每一个数,去看看能不能被第二个数整除,若能则答案++

代码实现:

class Solution {
public:int commonFactors(int a, int b) {vector<int>ans;int res=0;for(int i=2;i<=a;i++){if(a%i==0)ans.push_back(i);}for(int i=0;i<ans.size();i++){if(b%ans[i]==0)res++;}   return res+1;}
};

 还有一种方法,即寻找最大公约数,因为若想成为答案的一部分,每个数的约数一定为其最大公约数的因子.所以就转变成了求最大公约数的约数个数问题.

先来看看如何求最大公约数:

int gcd(int a,int b){int c=1;while(c){c=a%b;a=b;b=c;}return a;}

求出最大公约数后,就寻找其约数个数

这里简化了一下遍历范围,举一个简单的例子:2*3=6 所以2 3都为6的因子,他们都是成对出现的,所以只需要遍历到2的这一半就可以了.2*2!=6 说明其还有另一半,直接答案++即可.

int commonFactors(int a, int b) {int d=gcd(a, b);int ans=0;for(int i=1;i<=d/i;i++){if(d%i==0){ans++;if(i*i!=d)ans++;}}return ans;}

 公约数的个数与公约数之和:

这里简单复习一下,公约数的个数可以由质因数其指数个数+1再相乘得到

 

                              公约数之和可以由质因数每个指数个数相加再相乘得到

                               质因数可以由此方法得到:先判断这个数能否 被i整除,若能就一直除到不能被整除为止,记录次数.若最后x>1,则说明还有另一半没有被找到,则这个另一半即为x

#include<iostream>
using namespace std;
void divide(int x)
{for(int i=2;i<=x/i;i++)if(x%i==0){int s=0;while(x%i==0){x/=i;s++;}printf("%d %d\n",i,s);}if(x>1)printf("%d %d\n",x,1);puts("");return ;
}
int main()
{int n=0;cin>>n;while(n--){int x;cin>>x;divide(x);}return 0;
}

完结撒花：

🌈本篇博客的内容【LeetCode.每日一题 2427. 公因子的数目】已经结束。

🌈若对你有些许帮助，可以点赞、关注、评论支持下博主，你的支持将是我前进路上最大的动力。

🌈若以上内容有任何问题，欢迎在评论区指出。若对以上内容有任何不解，都可私信评论询问。

🌈诸君，山顶见！