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. 公因子的数目】已经结束。
🌈若对你有些许帮助，可以点赞、关注、评论支持下博主，你的支持将是我前进路上最大的动力。
🌈若以上内容有任何问题，欢迎在评论区指出。若对以上内容有任何不解，都可私信评论询问。
🌈诸君，山顶见！
