分解质因数算法总结
2024-01-07 17:36:16
知识概览
- n中最多只包含一个大于的质因子。
例题展示
题目链接
活动 - AcWing 系统讲解常用算法与数据结构,给出相应代码模板,并会布置、讲解相应的基础算法题目。https://www.acwing.com/problem/content/869/
题解
分解质因数可以用试除法解决,时间复杂度介于~之间(当时,时间复杂度为)。
代码
#include <iostream>
#include <algorithm>
using namespace std;
void divide(int x)
{
for (int i = 2; i <= x / i; i++)
if (x % i == 0) // i一定是质数
{
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("");
}
int main()
{
int n;
scanf("%d", &n);
while (n--)
{
int x;
scanf("%d", &x);
divide(x);
}
return 0;
}
参考资料
- AcWing算法基础课
文章来源:https://blog.csdn.net/u012181348/article/details/135425150
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!