学步园

Problem Description

Roma gave Chef an array of intergers.
Chef wants to make all integers in the array equal to 1.
In a single operation, he can select a prime number p and a subset of the integers, and then divide all of the integers in the subset by p.
Chef can make this operation only if every integer in the selected subset is divisible by p.

Please help Chef to make all the integers in the array equal to 1 with minimum number of operations.

Input

The first line of input contains a single integer T denoting the number of test cases. The description of Ttest cases follows.

The first line of each test case contains a single integer N denoting the length of the array that Roma gave Chef.

The second line contains N space-separated integers A₁, A₂, ..., A_N denoting the integers in the array.

Output

For each test case, output a single line containing one integer - the minimum number of operations needed to make all numbers equal to 1.

Constraints

• Subtask 1 (10 points): T = 5, 1 ≤ N ≤ 10⁵, 1 ≤ A_i ≤ 3
• Subtask 2 (40 points): T = 3, 1 ≤ N ≤ 10, 1 ≤ A_i ≤ 10⁶
• Subtask 3 (50 points): T = 3, 1 ≤ N ≤ 10⁵, 1 ≤ A_i ≤ 10⁶

Example

Input:
1
3
1 2 4

Output:
2

题解

素数筛法+分解质因数。O(n)的筛法可以顺便找出最小质因数。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
#define ll long long
#define MAXN 1000002
using namespace std;
int T,n,a[100002];//1000000
int mn[MAXN],pri[MAXN],zz;
int num[MAXN];
void prime()
{
	int i,j;
	for(i=2;i<=1000000;i++)
	   {if(!mn[i])
		   {mn[i]=i; zz++; pri[zz]=i;}
		for(j=1;j<=zz&&pri[j]*i<=1000000;j++)
		   {mn[pri[j]*i]=pri[j];
			if(i%pri[j]==0)break;
		   } 
	   }
}
void init()
{
	scanf("%d",&n);
	int i;
	for(i=1;i<=n;i++) scanf("%d",&a[i]); 
}
void work()
{
	int i,j,s,ct; ll ans=0;
	memset(num,0,sizeof(num));
	for(i=1;i<=n;i++)
	   {while(a[i]!=1)
	      {s=mn[a[i]]; ct=0;
		   while(a[i]%s==0) {a[i]/=s; ct++;}
		   num[s]=max(num[s],ct);
		  }
	   }
	for(i=2;i<=1000000;i++)
	   ans+=num[i];
	printf("%lld\n",ans);
}
int main()
{
	prime();
	scanf("%d",&T);
	while(T--) {init(); work();}
	return 0;
}