✨前言✨
在这个系列中，博主准备分享每日在万人千题社区打卡学习的算法。博主也是小白，因此也很能理解新手在刷题时的困惑，所以关注博主，每天学习一道算法吧。同时也欢迎大家加入万人千题习活动，正所谓：一个人可以走的很快，但一群人才能走的更远。
万人千题社区https://bbs.csdn.net/forums/hero?category=0&typeId=17913
讯享网https://bbs.csdn.net/forums/hero?category=0&typeId=17913
一、算法思想笔记
①算法基本定理：
对于任何整数n，都可以唯一分解成质数的乘积，将相同的质数合并后即可得到
②素因子筛选：
枚举法，埃氏筛，欧拉筛…… 枚举法+埃氏筛法+欧拉筛法（C语言实现）
③因子分解
我们在本章节中用枚举法试除每一个可能为素因子的数，实现因子的分解。
小技巧：判断素因子时枚举到 i * i <=n 即可
二、1492.n的第k个因子
n 的第 k 个因子https://leetcode-cn.com/problems/the-kth-factor-of-n/https://leetcode-cn.com/problems/the-kth-factor-of-n/①题目呈现
②代码操练
int kthFactor(int n, int k) { int i; int cnt = 0; int maxn=sqrt(n+1e-6);//防止浮点数不精确的影响 int factor[2*maxn]; factor[0]=0;//factor[0]记录因子的总组数 for( i = 1; i <= maxn; i++ ) { if(n % i==0 ) { factor[++factor[0]]=i;//别写成==了 } } if(maxn*maxn==n) { cnt=factor[0]*2-1;//cnt计算一共有多少个因子 } else cnt = factor[0]*2; if( k > cnt ) return -1; if(k <= factor[0] ) return factor[k]; else return n/factor[1+cnt-k]; }讯享网
思路：
1.因子分解过程中只需枚举到 i <= maxn 即可确定分解出几组因子
2.只需要再判断maxn*maxn==n，即可确定总组数是奇数个还是偶数个
3.在输出的时候若k>factor[0],只需根据因子的一一对称性即可解
结果：
三、1362.最接近的因数
最接近的因数https://leetcode-cn.com/problems/closest-divisors/https://leetcode-cn.com/problems/closest-divisors/
①题目呈现
②代码操练
讯享网/ * Note: The returned array must be malloced, assume caller calls free(). */ int Factor(int n) { int maxn=sqrt(n+1e-6); int i; for(i = maxn; i>=2;i--) { if(n % i == 0) break; } return i; } int* closestDivisors(int num, int* returnSize) { *returnSize=2; int n1 = 0;int n2 = 0; int*ans = (int *)malloc(sizeof(int)*2); n1 = Factor(num+1); n2 = Factor(num+2); if(( (num+1) / n1 - n1 ) < ( (num+2) / n2 -n2 )) { ans[0] = n1; ans[1] = (num+1) / n1; } else { ans[0] = n2; ans[1] =(num+2) / n2; } return ans; }
思路：
1.和上一道题类似，不同的是我们从 i = maxn开始递减，这样做的目的是尽快找到最接近的数字
结果：
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/50008.html