跳转至

暴力分解质因子

867.分解质因数

给点 \(n\) 个正整数 \(a_i\)，将每个数分解质因数，并安装质因数从小到大的顺序输出每个质因数的底数和质数。

对于每一个「大于 1」正整数都可以分解成 \(n = p_1^{k_1} \cdots p_n^{k_n}\):

  • \(p_1、p_2、p_3、\cdots 、p_n\) 是单调递增的；
  • 我们先用 \(i\) 从 \(2\) 开始往右遍历，若 \(n \bmod i == 0\)，则 \(i\) 就是 \(n\) 中最小的质因子；
  • 我们将 \(n\) 不断的除以 \(i\)，直到 \(n \bmod i \neq 0\) 为止；
  • \(i\) 接着往右边遍历，若 \(n \bmod i == 0\)，则我们又找到了一个次最小的质因子，然后不断的除以 \(i\)，直到不能整除为止；
  • 不断的执行上述步骤，就能确定出所有的质因子。

我们讨论一下该循环要什么时候退出，我们可以发现 \(i\) 只要去到 \(sqrt(n)\) 时就能基本确定质因子：

  • 对于任意一个大于 1 的正整数 \(n\) ，最多只能有一个大于 \(sqrt(n)\) 的质因子存在；
  • 基本所有的质因子 \(p\) 都小于或等于 \(sqrt(n)\);
  • \(i\) 的遍历范围最多为：\([2, sqrt(n)]\)

如果 \(n\) 是素数，则「时间复杂度」是最坏的：\(O(sqrt(n))\)。

代码参考：

// 分解质因子：get prime factor
vector<vector<int>> get_pf(int n)
{
    vector<vector<int>> ans;    
    if (n <= 1) return ans;
    for (int i = 2; i <= n / i; i ++)
    {
        if (!(n % i))
        {
            ans.push_back({i, 0});
            while (!(n % i))
            {
                n /= i; ans.back()[1] ++;
            }
        }
    }
    if (n > 1) ans.push_back({n, 1});
    return ans;
}
「867.分解质因数」代码参考

给点 \(n\) 个正整数 \(a_i\)，将每个数分解质因数，并安装质因数从小到大的顺序输出每个质因数的底数和质数。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>

using namespace std;
int debuggersum = 0;

// 即使是不成熟的尝试，

int n;

// 分解质因子：get prime factor
vector<vector<int>> get_pf(int n)
{
    vector<vector<int>> ans;    
    if (n <= 1) return ans;
    for (int i = 2; i <= n / i; i ++)
    {
        if (!(n % i))
        {
            ans.push_back({i, 0});
            while (!(n % i))
            {
                n /= i; ans.back()[1] ++;
            }
        }
    }
    if (n > 1) ans.push_back({n, 1});
    return ans;
}

void solve(void)
{
    scanf ("%d", &n);
    while (n --)
    {
        int t; scanf ("%d", &t);
        auto ans = get_pf(t);
        for (auto node : ans)
            printf ("%d %d\n", node[0], node[1]);
        puts("");
    }
}

// 也胜于胎死腹中的策略。

int main(void)
{
    ifstream fi; ofstream fo;
    fi.open("./lrq.in"); fo.open("./lrq.out");
    if (fi.is_open() && fo.is_open())
    {
        fo << "start running ..." << endl; fo.close(); fi.close();
        for (long long i = 1; i <= 4e8 + 2e7; i++);
        FILE *fin = freopen("./lrq.in", "r", stdin);
        FILE *fout = freopen("./lrq.out", "w", stdout);
        solve(); fclose(fin); fclose(fout);
    }
    else solve();

    return 0;
}