小单同学刚学习了一个数分解成几个素数（也叫质数）因子相乘的知识。
例如：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。
第一行两个数：a，b，中间用一个空格分隔。
一个整数，表示a和b相同的素（质）因子个数。
12 144
3
对于50%的数据，保证2≤a，b≤100
对于100%的数据，保证2≤a，b≤10000
syq命题。
#include<iostream> #include<cmath> #include<cstring> #include<cstdio> using namespace std; int a,b; int a1[10001],b1[10001]; int ans=0; int p1,p2; bool s1[10001],s2[10001]; int shai(int x)//判断是否为素数 { if(x==2) return 1; for(int i=2;i<=sqrt(x);i++) if(x%i==0) return 0; } int main() { cin>>a>>b; for(int i=2;i<=a;i++) { if(a==1) break;//到1之后就对答案没贡献了（MOD不了了） while(a%i==0) { if(shai(i)) a1[++p1]=i,a/=i;// } } for(int i=2;i<=b;i++) { if(b==1) break; while(b%i==0) { if(shai(i)) b1[++p2]=i,b/=i; } } for(int i=1;i<=p1;i++) for(int j=1;j<=p2;j++) if(a1[i]==b1[j]&&!s1[i]&&!s2[j])//判重 { s1[i]=1; s2[j]=1; ans++; } printf("%d",ans); return 0; }
原文：http://www.cnblogs.com/xiaoningmeng/p/5517276.html