SZU:A25 Favorite Number

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 $T(1 leq T leq 100)$ , the number of test cases. First line of each test case contains a integers $N(1 leq N leq 1, 024)$ . 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：

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <math.h>
 4 
 5 #define N   100000
 6 #define yes '1'
 7 #define no  '0'
 8 char flag[N+1];
 9 
10 void is_prime(int n)
11 {
12     int i, j;
13     memset(flag, yes, sizeof(flag));
14     flag[0]=flag[1]=no;
15     int len=sqrt(n)+1;
16     for(i=2; i<len; i++)
17     {
18         if(flag[i]==no) continue;
19         for(j=i+i; j<=n; j+=i)
20             flag[j]=no;
21     }
22 }
23 
24 int main(void)
25 {
26     int n;
27     ///find the primes from 1 to n(n<=N)
28     scanf("%d", &n);
29     is_prime(n);
30     for(int i=1; i<=n; i++)
31         if(flag[i]==yes)
32             printf("%8d", i);
33     printf("
");
34     return 0;
35 }

解题：

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <math.h>
 4  
 5 #define N   100050
 6 #define yes '1'
 7 #define no  '0'
 8 char flag[N];
 9  
10 void is_prime(int n)
11 {
12     int i, j;
13     memset(flag, yes, sizeof(flag));
14     flag[0]=flag[1]=no;
15     int len=sqrt(n)+1;
16     for(i=2; i<len; i++)
17     {
18         if(flag[i]==no) continue;
19         for(j=i+i; j<=n; j+=i)
20             flag[j]=no;
21     }
22 }
23 
24 
25 
26 int main()
27 {
28     int n;
29     int count;
30     int t,i,k,num;
31     int max;
32     scanf("%d",&t);
33     while (t--) {
34         scanf("%d", &n);
35         max=0;
36         for (i=0;i<n;++i) {
37             count=0;
38             scanf("%d",&num);
39  
40             is_prime(num);
41             for(i=1; i<=num; i++)
42                 if(flag[i]==yes){
43                     if(num%i==0)
44                     count++;
45             }
46             if(count>max) 
47             {
48                 max=count;
49                 k=num;
50             }
51             if (count==max)
52             {
53                    if (k>num) k=num;
54             }
55         }
56         printf("%d
",k);
57     }
58     return 0;
59 }

Winifred:

 1 #include <stdio.h>
 2 #include <string.h>
 3 bool f[100025];
 4 int T,p[100025];
 5 
 6 void getprime()
 7 {
 8     int i,j;
 9     memset(f,true,sizeof(f));
10     f[1]=false;
11     for (i=2;i<=100000;i++)
12     if (f[i])
13     {
14         for (j=i+i;j<=100000;j+=i) f[j]=false;
15     }
16     T=0;
17     for (i=2;i<=100000;i++)
18     if (f[i])
19     {
20         T++;
21         p[T]=i;
22     }
23 }
24 
25 int getdivnum(int x)
26 {
27     int ans=0,tmp=x;
28     for (int i=1;i<=T;i++)
29     {
30         if (tmp%p[i]==0)
31         {
32             ans++;
33             while (tmp%p[i]==0) tmp/=p[i];
34         }
35         if (p[i]>tmp) break;
36     }
37     return ans;
38 }
39 int main()
40 {
41     getprime();
42     int cas;
43     scanf("%d",&cas);
44     while (cas--)
45     {
46         int n;
47         scanf("%d",&n);
48         int Max=0,u;
49         for (int i=1;i<=n;i++)
50         {
51             int x;
52             scanf("%d",&x);
53             int t=getdivnum(x);
54             if (t>Max)
55             {
56                 Max=t;
57                 u=x;
58             }
59             else if (t==Max)
60             {
61                 if (u>x) u=x;
62             }
63         }
64         printf("%d
",u);
65     }
66     getprime();
67 }