题目描述： Haue的ACM比赛又开赛了，小z兴致勃勃的来参赛，小z本来想拿一个奖回去的，可一上来就被一个题目给弄晕了，“这是哈呀”，小z说道，“啥是素数，啥是最大公约数，啥又是最大素公约数？？”平日里，小z的老师已经将这些问题强调多次，可是健忘的小z却还是没有记住，于是他趴下睡着了，梦中见到了你，你告诉了他解题方法，然后他睡醒了，准备开始写题，又忘记了，于是你再次出现，直接将结果告诉了他，你还记得你告诉他的结果是什么吗？ 输入 一行，两个整数n和m（int范围内）
输出 一行，一个数字，表示n和m的最大素公约数。（最大素公约数，即公约数中是素数的最大的一个，如果两个数字不存在最大素公约数，输出-1）
样例输入 6 12
样例输出 3
题解
#include<stdio.h> int maxnum(int a,int b) //函数使用递归求最大公约数 { int t,num; while(b!=0) { num=a%b; a=b; b=num; } return a; } int primenum(int u) { int i; int t=0; for(i=2;i<u;i++)//判断从2开始至最大公约数 { if(u%i==0)//判断公约数是否还有约数 { u=u/i;//若有约数，则最大公约数不是素数，则进行约数替换 t=1;//t作为观测值 break; } } if(t==0) return u;//若没有约数返回main()函数 else primenum(u);//若有约数返回此函数继续执行 } int main() { int x,y,e,q; scanf("%d%d",&x,&y); e=maxnum(x,y); q=primenum(e); if(q==1) printf("-1"); else printf("%d",q); return 0; }本题核心思想还是结合求最大公约数和素数的判定。
