The Factor（数论规律题+求质因子）

Link：http://acm.hdu.edu.cn/showproblem.php?pid=5428

The Factor

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 688    Accepted Submission(s): 229

Problem Description

There is a sequence of  n  positive integers. Fancycoder is addicted to learn their product, but this product may be extremely huge! However, it is lucky that FancyCoder only needs to find out one factor of this huge product: the smallest factor that contains more than 2 factors（including itself; i.e. 4 has 3 factors so that it is a qualified factor）. You need to find it out and print it. As we know, there may be none of such factors; in this occasion, please print -1 instead. 

 

Input

The first line contains one integer  T (1≤T≤15) , which represents the number of testcases. 

For each testcase, there are two lines:

1. The first line contains one integer denoting the value of  n (1≤n≤100) .

2. The second line contains  n  integers  a1,…,an (1≤a1,…,an≤2×109) , which denote these  n  positive integers. 

 

Output

Print  T  answers in  T  lines.

 

Sample Input

  
  
  

   
   
   2
   
   
   
3
   
   
   
1 2 3
   
   
   
5
   
   
   
6 6 6 6 6
  
  
  

 

Sample Output

  
  
  

   
   
   6
   
   
   
4
  
  
  

 

Source

BestCoder Round #54 (div.2)

 

官方题解：

The Factor

对于每一个数字，它有用的部分其实只有它的所有质因子（包括相等的）。求出所有数的所有质因子中最小的两个，相乘就是答案。如果所有数字的质因子个数不到两个，那么就是无解。时间复杂度$O(n\ast sqrt(a))$。

AC code：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#define PI acos(-1.0)
#define LINF 1000000000000000000LL
#define eps 1e-8
#define LL long long
#define MAXN 1000010 
#define MOD 9901
using namespace std;
const int INF=0x3f3f3f3f;
//******************************************
//素数筛选和合数分解
int cnt;//质因子个数
long long ans;
LL b[MAXN];
LL a[111];
int main()
{
	int A,B,n;
	int t,i;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		cnt=0;
		for(i=1;i<=n;i++)
		{
			scanf("%I64d",&a[i]);
			for(int j=2;(LL)j*j<=a[i];j++){
				 while(a[i]%j==0){
				 	b[++cnt]=j;
				 	a[i]/=j;
				}
			}
			if(a[i]!=1){
				b[++cnt]=a[i];
			}
		}
		if(cnt>=2)
		{
			sort(b+1,b+cnt+1); 
			printf("%I64d\n",b[1]*b[2]);
		}
		else
		{
			printf("-1\n");
		}
	}
    return 0;
}