开发者社区云计算文章正文

分解质因数答疑

2023-11-22 71

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 为什么n % i == 0就是质数因为在枚举到i之前已经把n中2到i-1的质因子除干净了，此时n中不含2到i-1的质因子，由于n为i的倍数，所以i中也不包含2到i-1的质因子。如果i可以整除前面的i - 1中的数那么i = x * (i - 1),n = x2 * (x * (i - 1));矛盾了为什么只需要枚举到根号N

什么是分解质因数：

题目描述:

输入样例：

2
6
8

输出样例：

2 1
3 1
2 3

思路：

为什么只需要枚举到根号N

为什么n % i == 0就是质数

因为在枚举到i之前已经把n中2到i-1的质因子除干净了，此时n中不含2到i-1的质因子，由于n为i的倍数，所以i中也不包含2到i-1的质因子。如果i可以整除前面的i - 1中的数那么i = x * (i - 1),n = x2 * (x * (i - 1));

矛盾了

代码：

#include <iostream>
using namespace std;
void divide(int n)
{
    for (int i = 2; i <= n / i; i++) 
        {
            if (n % i == 0)
            {
                int s = 0;
                while (n % i == 0)
                    {
                        n /= i;
                        s++;
                    }
                cout << i << " " << s << endl;
            }    
        }
    //单独处理大于根号N的质因数
    if (n > 1)  cout << n << " " << 1 << endl;
    cout << endl;
}
int main()
{
    int n;
    cin >> n;
    while (n--)
        {
            int x;
            cin >> x;
            divide(x);
        }
    return 0;
}