Smallest multiple
2023-03-14 10:17:14 时间
#include<iostream> #include<algorithm> using namespace std; int lcm(int a ,int b) { int big=max(a,b); int small=min(a,b); int max=a*b; for(int i=big; i<max; i+=big) { if(i%small==0) return i; } return max; } int main() { int sum,a=1,b=2; while(b!=20) { sum=lcm(a,b); a=sum; b++; } cout<<sum<<endl; return 0; }
https://projecteuler.net/problem=5
求1-20的最小公倍数。
求两个数a,b的最小公倍数嘛,先取出其中较大的那个比如a,然后再用k*a去试探能否被较小那个数整除,其中,k是从1开始的自然数 k*a<a*b。
另外一种比较好的方法,以n取10为例
2,3,4,5,6,7,8,9,10 (1没有什么意义,忽略掉了)
将这些数字分解质因数:
2, 3, 2*2, 5, 2*3, 7, 2*2*2, 3*3, 2*5
这些质数分别是2, 3, 5, 7
最终答案可以表示为:
2^a * 3^b * 5^c * 7^d (其中,x^y表示x的y次方)
其中的英文字母表示在上面分解质因数时所得到的表达式中质因数在同一个表达式中出现的次数的最大值。
质因数2出现次数最多是在8=2*2*2中,其出现了3次,所以a为3。
同理可得到:2^3 * 3^2 * 5^1 * 7^1 = 2520。
相关文章
- 在 Go 里用 CGO?这 7 个问题你要关注!
- 9款优秀的去中心化通讯软件 Matrix 的客户端
- 求职数据分析,项目经验该怎么写
- 在OKR中,我看到了数据驱动业务的未来
- 火山引擎云原生大数据在金融行业的实践
- OpenHarmony富设备移植指南(二)—从postmarketOS获取移植资源
- 《数据成熟度指数》报告:64%的企业领袖认为大多数员工“不懂数据”
- OpenHarmony 小型系统兼容性测试指南
- 肯睿中国(Cloudera):2023年企业数字战略三大趋势预测
- 适用于 Linux 的十大命令行游戏
- GNOME 截图工具的新旧截图方式
- System76 即将推出的 COSMIC 桌面正在酝酿大变化
- 2GB 内存 8GB 存储即可流畅运行,Windows 11 极致精简版系统 Tiny11 发布
- 迎接 ecode:一个即将推出的具有全新图形用户界面框架的现代、轻量级代码编辑器
- loongarch架构介绍(三)—地址翻译
- Go 语言怎么解决编译器错误“err is shadowed during return”?
- 敏捷:可能被开发人员遗忘的部分
- Denodo预测2023年数据管理和分析的未来
- 利用数据推动可持续发展
- 在 Vue3 中实现 React 原生 Hooks(useState、useEffect),深入理解 React Hooks 的