質因數分解那裡應該可以更快，但我不知道怎麼修正，如果有人知道可以回覆一下，謝謝

#include<bits/stdc++.h>
using namespace std;

int gcd(int a,int b);
int main() {
    ios::sync_with_stdio(0);cin.tie(0);
	
    const int N=65536+1;
	vector<int> prime;
	vector<int> spf(N); //smallest prime factor
	spf[0]=spf[1]=-1;

	//線性篩
	for(int i=2; i<N; i++) {
		if(spf[i]==0) {
			prime.push_back(i);
			spf[i]=i;
		}
		//for(int j:prime)是複製參數 for(const int &j :prime)是直接參照，比較快
		for(const int &j:prime) {
			if (1LL * i * j >= N) break;
            if (j > spf[i]) break;
			spf[i*j]=j;
		}
	}
	
	
	//主程式
	int n;
	cin >> n;
	while(n--) {
		int a,b;
		cin >> a >> b;
	    
	    //質因數分解
	    vector<int> prime_factor;
	    int temp=a;
	    while(spf[temp]>1){
	        prime_factor.push_back(spf[temp]);
	        temp/=spf[temp];
	    }
	    int t=1;
	    for(int i=0;i<prime_factor.size()-1;i++){
	        if(prime_factor[i]==prime_factor[i+1])t++;
	        else{
	            if(t==1)cout << prime_factor[i];
	            else cout << prime_factor[i] << "^" << t;
	            cout << "*";
	            t=1;
	        }
	    }
	    if(t==1)cout << prime_factor[prime_factor.size()-1];
	    else cout << prime_factor[prime_factor.size()-1] << "^" << t;
	    
	    cout << " , ";
	    
	    //最大公因數(輾轉相除法)
	    int max_commom_factor=gcd(a,b);
	    cout << max_commom_factor ;
	    cout << " , ";
	    
	    //判斷gcd是否為質數
	    cout << ((spf[max_commom_factor]==max_commom_factor) ? "Y" : "N");cout << endl;
	}
	
}

//輾轉相除法(遞迴)
int gcd(int a,int b) {
	return b==0 ? a : gcd(b, a%b);
}