先筛出所有质数，再做试除法

#include <iostream>

using namespace std;

const int N = 50000;

int primes[N] , cnt;
bool st[N];

void init(int n)
{
    for(int i = 2 ; i <= n ; i++)
    {
        if(!st[i]) primes[cnt++] = i;

        for(int j = 0 ; primes[j] <= n / i ; j++)
        {
            st[primes[j] * i] = true;

            if(i % primes[j] == 0) break;
        }
    }
}

int main()
{
    int T;
    cin >> T;

    init(N - 1);
    while(T--)
    {
        int x;
        cin >> x;
        for(int i = 0 ; primes[i] <= x / primes[i] ; i++)
        {
            int p = primes[i];
            if(x % p == 0)
            {
                int s = 0;
                while(x % p == 0) s++ , x /= p;
                cout << p << ' ' << s << endl;
            }
        }
        if(x > 1) cout << x << ' ' << 1 << endl;
        cout << endl;
    }
    return 0;
}