Hrbust1328 相等的最小公倍數 (篩素數，素因子分解）

題意：

求解An 與 An-1是否相等。

n分為兩個情況——

1.n為素數，

2.n為合數。

= =好像說了個廢話。。素數的時候，可以直接輸出no，因為素數不可能和An-1相等。合數的時候，如果n是a^b次方，那麼也是NO。原因很簡單，之前數字的最小公倍數的n的因子次方數，不能超過n的次方數。

//============================================================================
// Name        : 數論問題.cpp
// Author      :
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include 
#include 
#include 

using namespace std;
#define lln long long int
#define MAXN 1000001

bool vis[MAXN];
int prime[100000];
int p;

void Prime()
{
    //0為不是合數，1為是合數
    memset(vis, 1, sizeof(vis));
    p = 0;
    int i, j;
    for(i = 2; i < MAXN; i++)
    {
        if(vis[i])
        {
            prime[p++] = i;
            for(j = 2 * i; j < MAXN; j += i)
                vis[j] = 0;
        }
        else
            continue;
    }
}

void ace(){
	//init
	Prime();
	//work point
	int t, i;
	//num
	int a;
	int num;

	cin >> t;
	while(t--){
		scanf(%d, &a);
		if(a == 2)
		{
            printf(NO
);
            continue;
        }
		if(vis[a])
            printf(NO
);
        else
        {
            num = 0;
            for(i = 0 ; i <= p; i++)
            {
                if(a % prime[i] == 0)
                {
                    num++;
                    while(a % prime[i] == 0)
                        a /= prime[i];
                }
                if(a == 1)
                    break;
            }
            if(num >= 2)
                printf(YES
);
            else
                printf(NO
);
        }
	}
}

int main() {
	ace();
	return 0;
}