侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 551 篇文章
  • 累计创建 117 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【数学】分解质因数

GabrielxD
2022-12-02 / 0 评论 / 0 点赞 / 57 阅读 / 1,033 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-12-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

867. 分解质因数


给定 nn 个正整数 aia_i ,将每个数分解质因数,并按照质因数从小到大的顺序输出每个质因数的底数和指数。

输入格式

第一行包含整数 nn

接下来 nn 行,每行包含一个正整数 aia_i

输出格式

对于每个正整数 aia_i ,按照从小到大的顺序输出其分解质因数后,每个质因数的底数和指数,每个底数和指数占一行。

每个正整数的质因数全部输出完毕后,输出一个空行。

数据范围

1n1001 \le n \le 100 ,
2ai2×1092 \le a_i \le 2 \times 10^9

输入样例:

2
6
8

输出样例:

2 1
3 1

2 3

解题

方法一:试除法

前置

质因数分解(Prime Factorization)

是将一个合数写成几个质数相乘的形式,其中每个质数都是这个合数的因数。例如 45=32×545=3^2 \times 5 。根据算术基本定理,这样的分解结果应该是独一无二的。

测试样例解释

输入两个数:6688,分解质因数:6=21×316=2^1 \times 3^18=238 = 2^3

所以对于 66 输出:

2 1
3 1

对于 88 输出:

2 3

思路

朴素解法

若要将数 nn 进行质因数分解,从小到大(2n2 \dots n)枚举 nn 的所有因数,求出该因数的次数,输出该因数与其次数。
由以上思路可以写出如下代码:

void pf(int n) {
    for (int i = 2; i <= n; ++i) {
        // 枚举因数
        if (n % i == 0) {
            int s = 0;
            // 求次数
            while (n % i == 0) {
                n /= i;
                ++s;
            }
            System.out.println(i + " " + s);
        }
    }
}

我们需要分解质因数,但枚举的 i 是所有因数而不是质因数,如何证明 in % i == 0 成立时一定是质因数?
——反证法:假如 i 是一个合数,那么它一定也可以分解成多个质因子相乘的形式,而此时 in 的因子成立,所以这多个质因子既是 i 的质因子又 n 的质因子并且比 i 要小,而比 i 小的数在之前的循环过程中一定是被条件除完了的,也就是说质因子的个数是 00,此时产生了矛盾,所以 i 不可能是合数,只可能是质数。

优化

有性质:nn 中最多只包含一个大于等于 n\sqrt{n} 的质因子。(易证:若 nn 可以被分解成两个大于n\sqrt{n} 的质因数,则这两个质因数相乘的结果大于 nn ,与事实矛盾)

所以枚举的时候可以只枚举 n\le \sqrt{n} 的因数,最后剩下的 nn 如果大于 11,那么剩下的 nn (循环过程中 nn 会变)就是那个大于等于 n\sqrt{n} 的质因子。

代码

import java.util.*;
import java.io.*;

public class Main {
    static void pf(int n) {
        for (int i = 2; i <= n / i; ++i) {
            if (n % i == 0) {
                int s = 0;
                while (n % i == 0) {
                    n /= i;
                    ++s;
                }
                System.out.println(i + " " + s);
            }
        }
        if (n > 1) System.out.println(n + " 1");
    }
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        while (n-- > 0) {
            in.nextToken();
            pf((int) in.nval);
            System.out.print("\n");
        }
    }
}
#include <iostream>

using namespace std;

void pf(int n) {
    for (int i = 2; i <= n / i; ++i) {
        if (n % i == 0) {
            int s = 0;
            while (n % i == 0) {
                n /= i;
                ++s;
            }
            printf("%d %d\n", i, s);
        }
    }
    if (n > 1) printf("%d 1\n", n);
}

int main() {
    int n;
    scanf("%d", &n);
    while (n--) {
        int a;
        scanf("%d", &a);
        pf(a);
        puts("");
    }
    
    return 0;
}

时间复杂度:O(logN)O(\log{N})(最好) O(n)O(\sqrt{n})(最坏)。

0

评论区