题目描述 Description
小单同学刚学习了一个数分解成几个素数（也叫质数）因子相乘的知识。
例如：12=2*2*3；25=5*5；144=2*2*2*2*3*3······等，比如，第一个表达式，说明12这个整数可以分解出2、2、3这三个质数因子。老师给他布置了一个作业，小单看来看去，怎么都不会做，只好虚心求教各位同学（他自己睡觉去了！）
问题是这样的：已知两个正整数a，b；请问a，b相同的素（质）因子有几个。请输出个数。例如：12与144 相同的素（质）因子为2,2,3；则输出3。12与25 相同的素（质）因子没有；则输出0。
输入描述 Input Description
第一行两个数：a，b，中间用一个空格分隔。
输出描述 Output Description
一个整数，表示a和b相同的素（质）因子个数。
样例输入 Sample Input
12 144
样例输出 Sample Output
3
数据范围及提示 Data Size & Hint
对于50%的数据，保证2≤a，b≤100
对于100%的数据，保证2≤a，b≤10000
#include <iostream> using namespace std; int n,m,ans; int prime(int n)
{ //求素数，大家都知道吧？
int i;
if (n== || n==)return ;
if (n==)return ;
for(i=;i*i<n;i++)
if(n%i==)return ;
if(i*i==n)return ;
return ;
} int solve()
{ //求公因数
int a=n,b=m,c=a%b;
while(c!=){ //辗转相除法
a=b;
b=c;
c=a%b;
}
return b;
} void work(int n)
{ //求给n,m的公因数分解，然后判断如果是质数，那么就+1
int i=;
while(n!=){
if(n%i== && prime(i)==){ans++;n/=i;}
else i++;
}
cout<<ans<<endl; //输出
} int main(){
int s;
cin>>n>>m; //读入
s=solve();
work(s);
return ;
}