【acwing算法基礎課】 數學知識 分解質因數

題目來源：分解質因數

題目描述

給定n個正整數ai，将每個數分解質因數，并按照質因數從小到大的順序輸出每個質因數的底數和指數。

輸入格式

第一行包含整數n。

接下來n行，每行包含一個正整數ai。

輸出格式

對于每個正整數ai,按照從小到大的順序輸出其分解質因數後，每個質因數的底數和指數，每個底數和指數占一行。

每個正整數的質因數全部輸出完畢後，輸出一個空行。

資料範圍

1≤n≤100,

1≤ai≤2∗109

輸入樣例：

2
6
8
           

輸出樣例：

2 1
3 1

2 3
           

思路

周遊所有質數，然後把它除幹淨，計算他的個數就好了

一些注意點：

1. 周遊所有質數，但是我們實際寫的時候沒有去周遊所有的質數，而是周遊了所有的數。因為我們向下周遊的時候絕對不會包含和數 。例如我們是從2開始周遊的，那麼我們會把x中所有的2全部除幹淨了，那麼後續所有的因數含有2的數都不會在被我們選中了，因為它顯然不可能整除x了，其他的同理，是以我們在周遊的時候隻會選中質數了
2. 我麼在枚舉元素的時候沒有枚舉全部的數，而是枚舉了一半的數。因為顯然x的質因數，或者說的廣泛一點，x的因數，大于sprt(x)的最多隻可能是一個，是以我們在後面特判一下就好了

代碼

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int n,x;
    cin>>n;
    while(n--)
    {
        cin>>x;
        for(int i=2;i<=x/i;i++) //細節 寫成i<=x/i 比i*i<=x安全 比i<=sqrt(x)快
        {
            //計算質因數的個數，順便把x中的該質因數 除幹淨
            if(x%i==0)
            {
                int s=0;
                while(x%i==0) x/=i,s++;
                cout<<i<<' '<<s<<endl;
            }
        }
        if(x>1) cout<<x<<' '<<1<<endl;
        cout<<endl;
    }
    return 0;
}