公共素数因数

题目描述 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

syq命题。

//利用数字的Ascall码，判断出现次数

#include <iostream> #include <cstdio> #include <cmath> using namespace std; int main() { int map[100]={0}; int a[256]={0}; int b[256]={0}; int x,y; int sum=0; int i,j,k=0; for(i=2;i<=100;i++) { int s=sqrt(i); for(j=2;j<=s;j++) { if(i%j==0) break; } if(j>s) map[k++]=i; } int t; scanf("%d%d",&x, &y); for(i=0;i<k;i++) { t=0; if(x==0||y==0) break; if(x%map[i]==0) { t=1; x/=map[i]; a[map[i]]++; } if(y%map[i]==0) { t=1; y/=map[i]; b[map[i]]++; } if(t==1) i--; } for(i=0;i<256;i++) { if(a[i]>=b[i]&&b[i]!=0) sum+=b[i]; if(a[i]<b[i]&&a[i]!=0) sum+=a[i]; } printf("%d\n",sum); return 0; }