学步园

相等的最小公倍数

Time Limit: 1000 MS Memory Limit: 65536 K Total Submit: 145(55 users) Total Accepted: 63(44 users) Rating:  Special Judge: No

Description

定义An为1，2，…，n的最小公倍数，例如，A1 = 1，A2 = 2，A3 = 6，A4 = 12，A5 = 60，A6 = 60。 请你判断对于给出的任意整数n，An是否等于An – 1。

Input

本题有多组测试数据，输入的第一行是一个整数T代表着测试数据的数量，接下来是T组测试数据。 对于每组测试数据： 第1行 包含一个整数n (2 ≤ n ≤ 106)。

Output

对于每组测试数据： 第1行 如果An等于An-1则输出YES否则输出NO。

Sample Input

1 6

Sample Output

YES

Source

哈理工2012春季校赛热身赛 2012.04.03

Author

齐达拉图@HRBUST

首先判断该数n是否为素数，，是素数的话，，An  An-1不可能相等，，因为An会比An-1 乘上一个更大的新素数。。

然后在n不是素数的前提下，，判断n是否存在 一对互素的因子..即n=a*b（a，b互素）（即gcd(a,b)==1）.存在则输出YES 

/**怎么判断相邻两个数的lcm是否相等.**/
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int gcd(int a,int b)
{
    if(b==0) return a;
    else    return gcd(b,a%b);
}
int main()
{
    int T,n;
    scanf("%d",&T);
    while(T--)
    {
        int i;
        bool p=true;
        scanf("%d",&n);
        int temp=(int)sqrt((double)n);
        if(n==2)
        {
            printf("NO\n");continue;
        }
        for(i=2;i<=temp;i++)
        if(n%i==0) break;
        if(i==temp+1)
        {
            printf("NO\n");continue;
        }
        for(i=2;i<=temp;i++)
        {
            if(n%i==0)
            {
                int q=n/i;
                if(gcd(q,i)==1)
                {
                    p=false;break;
                }
            }
        }
        if(p) printf("NO\n");
        else printf("YES\n");
    }
    return 0;
}