2955. Familial Numbers

单点时限: 2.0 sec

内存限制: 256 MB

任何一个大于 1 的正整数都可以唯一分解成若干个质数的乘积。例如:18 可以分解成 233,2,3,3 是 18 的三个质因子。如果两个正整数至少有一个相同的质因子,则称这两个整数具有 “ 家族性 ”。例如,130 和 150 具有 “ 家族性 ”,因为它们有相同的质因子 2 和 5。而 51 和 109 就不具有 “ 家族性 ”。

现任意给定两个正整数,请回答它们是否具有 “ 家族性 ”,如果有 “ 家族性 ”,则回答 Yes,同时输出它们的最小相同质因子,否则回答 No

输入格式

第 1 行:整数 $T$ ($1 \le T \le 10$) 为问题数

第 2 ∽ T+1 行:每行为每个问题中的两个由一个空格分隔的正整数 $N$ 和 $M$ $(2 \leqslant N,M\leqslant 10000)$。

输出格式

对于每个问题,第一行输出问题的编号(0 开始编号,格式:case #0: 等),第二行如果 $N,M$ 具有 “ 家族性 ”,则输出 Yes,一个空格,接着输出 $N$ 和 $M$ 的最小相同质因子;否则输出 No。行末尾输出一个换行符。

样例

Input
2
130 150
51 109
Output
case #0:
Yes 2
case #1:
No

572 人解决,625 人已尝试。

780 份提交通过,共有 1753 份提交。

1.1 EMB 奖励。

创建: 8 年,2 月前.

修改: 1 年,10 月前.

最后提交: 5 天,16 小时前.

来源: 2012年程序设计实践第8次上机考试

题目标签