Judge Info
- Memory Limit: 32768KB
- Case Time Limit: 10000MS
- Time Limit: 10000MS
- Judger: Number Only Judger
Description
Frog Frank likes 30 more than likes 40, yet he likes 12 and 39 equally. This is because he likes numbers that have a lot of different prime factors. For example, 30 have 3 prime factors (2,3 and 5) and 40 have 2(2 and 5) only. A prime number is a number that can be divided evenly only by itself and 1.
Task
You are given a list of numbers, find out which of the numbers Frank likes most. If there are more than one solutions, output the smallest.
Input
The first line of input contains 
, the number of test cases. First line of each test case contains a integers 
. The following line contains N positive integers, all of them are not greater than 100, 000.
Output
For each test case, print a line contains the solution.
Sample Input
2
10
3 5 7 9 11 13 15 17 19 21
11
2 4 6 8 10 13 39 105 200 201 143
Sample Output
15
105 解题思路：素数筛选 算法 from dd：
#include <stdio.h>
#include <string.h>
#include <math.h> #define N 100000
#define yes '1'
#define no '0'
char flag[N+]; void is_prime(int n)
{
int i, j;
memset(flag, yes, sizeof(flag));
flag[]=flag[]=no;
int len=sqrt(n)+;
for(i=; i<len; i++)
{
if(flag[i]==no) continue;
for(j=i+i; j<=n; j+=i)
flag[j]=no;
}
} int main(void)
{
int n;
///find the primes from 1 to n(n<=N)
scanf("%d", &n);
is_prime(n);
for(int i=; i<=n; i++)
if(flag[i]==yes)
printf("%8d", i);
printf("\n");
return ;
}
解题：
#include <stdio.h>
#include <string.h>
#include <math.h> #define N 100050
#define yes '1'
#define no '0'
char flag[N]; void is_prime(int n)
{
int i, j;
memset(flag, yes, sizeof(flag));
flag[]=flag[]=no;
int len=sqrt(n)+;
for(i=; i<len; i++)
{
if(flag[i]==no) continue;
for(j=i+i; j<=n; j+=i)
flag[j]=no;
}
} int main()
{
int n;
int count;
int t,i,k,num;
int max;
scanf("%d",&t);
while (t--) {
scanf("%d", &n);
max=;
for (i=;i<n;++i) {
count=;
scanf("%d",&num); is_prime(num);
for(i=; i<=num; i++)
if(flag[i]==yes){
if(num%i==)
count++;
}
if(count>max)
{
max=count;
k=num;
}
if (count==max)
{
if (k>num) k=num;
}
}
printf("%d\n",k);
}
return ;
}
Winifred:
#include <stdio.h>
#include <string.h>
bool f[];
int T,p[]; void getprime()
{
int i,j;
memset(f,true,sizeof(f));
f[]=false;
for (i=;i<=;i++)
if (f[i])
{
for (j=i+i;j<=;j+=i) f[j]=false;
}
T=;
for (i=;i<=;i++)
if (f[i])
{
T++;
p[T]=i;
}
} int getdivnum(int x)
{
int ans=,tmp=x;
for (int i=;i<=T;i++)
{
if (tmp%p[i]==)
{
ans++;
while (tmp%p[i]==) tmp/=p[i];
}
if (p[i]>tmp) break;
}
return ans;
}
int main()
{
getprime();
int cas;
scanf("%d",&cas);
while (cas--)
{
int n;
scanf("%d",&n);
int Max=,u;
for (int i=;i<=n;i++)
{
int x;
scanf("%d",&x);
int t=getdivnum(x);
if (t>Max)
{
Max=t;
u=x;
}
else if (t==Max)
{
if (u>x) u=x;
}
}
printf("%d\n",u);
}
getprime();
}