小工具知识网

当前位置: 首页 > 行业知识 > 【算法基础】分解质因数

行业知识

【算法基础】分解质因数

2026-11-16 14:11:57 来源:互联网转载

文章目录

  • 什么是分解质因数
  • 具体案例
    • 输入格式
    • 输出格式
    • 数据范围
    • 原理讲解
      • 原始方法
      • 转换思路
      • 利用试除法判定质数的思路
      • 为什么不需要单���判断是否为质数

        什么是分解质因数

        分解质因数是指将一个合数用质因数相乘的形式表示出来,即将一个合数分解为若干个质数的乘积。其中每个质数都是这个合数的因数。例如,将30分解质因数,得到2×3×5,即将30表示为2、3、5三个质数的乘积。分解质因数只针对合数,对于质数和1,不需要进行分解质因数。


        具体案例

        给定 n n n 个正整数 a i a_i ai​,将每个数分解质因数,并按照质因数从小到大的顺序输出每个质因数的底数和指数。

        输入格式

        第一行包含整数 n n n。

        接下来 n n n 行,每行包含一个正整数 a i a_i ai​。

        输出格式

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

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

        数据范围

        1 ≤ n ≤ 100 1≤n≤100 1≤n≤100,

        2 ≤ a i ≤ 2 × 1 0 9 2≤a_i≤2×10^9 2≤ai​≤2×109

        输入样例:

        268

        输出样例:

        2 13 12 3

        原理讲解

        原始方法

        原始的分解质因数的方法,是从小到大遍历所有小于n的数i,如果n % i == 0 且i为素数,那么i就是其中的一个质因数。

        按照这样的思路,我们只需要判断一次取余运算,判断一次素数。但是对于这道题的数据范围,一定会TLE。

        转换思路

        由于这道题还需要求出每个质因数的指数,那每次找到这个质因数之后,让n不停的除这个数i,直到除完为止,每除一次就表示次数+1

        这样就不需要把n遍历完,每找到一个素数k,n会减小1~k^s倍

        但是每次除法的过程也会有s次操作,数据范围仍然不允许

        利用试除法判定质数的思路

        可以把试除的时间复杂度降到O(sqrt(n))

        只需要判断sqrt(n)以内的质因数,但是sqrt(n)~n之间可能存在质因数且最多一个,所以在遍历完之后需要判断n是否被除尽,如果还有剩,那剩下的这个一定是一个质因数。

        为什么不需要单独判断是否为质数

        这其实用到了埃氏筛法筛素数的一个原理:

        我们每判断完一个素数x,就在2 - i-1之间把x的倍数筛了一遍了,于是在2 - i-1之间就不存在x的倍数了

        反证法证一下:

        假设我们遍历到一个数i是一个合数,那么它可以分解质因数,那么在2 - i-1之间就一定可以找到一个质数是i的因数,而根据我们的算法,前面所有遇到的质数已经把该质数的倍数除干净了,所以不存在任何一个质数的倍数,所以它在前面找不到一个质因数,所以它一定不是合数,与假设相矛盾,所以它一定是质数。

        #includeusing namespace std;void pide(long long n){    // int x = sqrt(n);    int i;    for(i = 2; i         if(n % i == 0){            int s = 0;            while(n % i == 0){                n /= i;                s++;            }            cout     int n;    cin  n;    while(n--){        long long a;        cin  a;        pide(a);    }    return 0;}

上一篇:Opensips,探究未来通信解决方案的首选之路

下一篇:tk域名怎么解读