【算法基础】分解质因数

文章目录

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

      ---

      什么是分解质因数

      分解质因数是指将一个合数用质因数相乘的形式表示出来，即将一个合数分解为若干个质数的乘积。其中每个质数都是这个合数的因数。例如，将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

      输入样例：

      2
      6
      8
      

      输出样例：

      2 1
      3 1
      2 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 divide(long long n){ // int x = sqrt(n);
          int i;
          for(i = 2; i <= n / i; i++){ if(n % i == 0){ int s = 0;
                  while(n % i == 0){ n /= i;
                      s++;
                  }
                  cout << i << " " << s << endl;
              }
          }
          if(n > 1) cout << n << " " << 1 << endl; 
          cout << endl;
      }
      int main(){ int n;
          cin >> n;
          while(n--){ long long a;
              cin >> a;
              divide(a);
          }
          return 0;
      }
      

      作者：为梦而生

      链接：https://www.acwing.com/activity/content/code/content/7348563/

      来源：AcWing

      著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。