高中生程式解題:b534: 質因數、最大公因數－資工趴趴熊的小天地

Content

這是全國中等學校102學年度商業類科學生技藝競賽模擬題P31「程式設計」的試題加一點點修改

輸入兩個正整數，寫一程式完成以下三個要求：
(1)求第一個數字a的質因數乘積式，所有質因數由小至大列出，質因數2次方以上的加^代表幾次，
(2)求 a 與 b 的最大公因數， (3)判斷其最大公因數是否為質數，1不算質數，是則輸出Y，否則輸出N。

Input

第一列輸入一個正整數 n ， 1<=n<=5，接著 n 列，每列兩個整數 a,b 以空白隔開， 2<= a,b <=65536

Output

每一列依題意輸出三組資料，中間以逗號隔開，且逗號左右各空一空格，質因數乘積式中間無空格

Sample Input #1

Sample Output #1

2^2*3*5*547 , 20 , N
2^5*3^2 , 144 , N
2^2*3 , 6 , N
17 , 1 , N
2*3^2 , 3 , Y

C++:

#include <iostream>
using namespace std;

void integer_factorization(int n){ //求質因數分解  
	int i = 2;
    while( n > 1 )
    {
        int acc=0;
        bool flag=true;
        while( n%i == 0 )
        {
            if(flag==true){
                cout << i ;
                flag=false; 
            }           
            acc+=1;
            n = n/i;
        }
        if(flag==false){
        	if(acc>1)cout<<"^"<<acc;
            if(n>1)cout<<"*";
        }
        flag=true;
        i+=1;
    }
}

int  gcd(int a,int b){ //求最大公因數 
	if(b>a){
		swap(a,b);
	}
	while(b!=0){
		int temp=b;
		b=a%b;
		a=temp;
	}
	cout<<a;
	return a;
}



int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int count;
	cin>>count;
	while(count--){
		int m,n;
	    while(cin>>n>>m){
		    integer_factorization(n);	
		    cout<<" , ";
		    int e=gcd(n,m);
		    cout<<" , ";
		    
		    bool flag=true;
		    if(e!=1){
		    	for(int i=2;i<e;i++){
		    		if(e%i==0){
			    		cout<<"N\n";
			    		flag=false;
			    		break;
					}	
				}
			}
			if(e==1){cout<<"N\n";flag=false;}
			if(flag==true){cout<<"Y\n";}			
		}    		
	}   
    return 0;
}