題干：

To improve the organization of his farm, Farmer John labels each of his N (1 <= N <= 5,000) cows with a distinct serial number in the range 1..20,000. Unfortunately, he is unaware that the cows interpret some serial numbers as better than others. In particular, a cow whose serial number has the highest prime factor enjoys the highest social standing among all the other cows.?

(Recall that a prime number is just a number that has no divisors except for 1 and itself. The number 7 is prime while the number 6, being divisible by 2 and 3, is not).?

Given a set of N (1 <= N <= 5,000) serial numbers in the range 1..20,000, determine the one that has the largest prime factor.

Input

* Line 1: A single integer, N?

* Lines 2..N+1: The serial numbers to be tested, one per line

Output

* Line 1: The integer with the largest prime factor. If there are more than one, output the one that appears earliest in the input file.

Sample Input

4 36 38 40 42

Sample Output

38

Hint

OUTPUT DETAILS:?
19 is a prime factor of 38. No other input number has a larger prime factor.

解題報告：

? ?正解的代碼顯然是打表預處理nlogn，單組樣例o(n)。。。。

? ?第一個的做法是nloglogn打表，然后單組樣例最壞復雜度n*20000（也就是每一次都是一個素數。、。。）

AC代碼1：（860ms）

#include<cstdio> #include<cstring> #include<iostream> #define MAX 20000 + 18//求MAX范圍內的素數 using namespace std; long long su[MAX],cnt; bool isprime[MAX]; void prime() { cnt=1; memset(isprime,1,sizeof(isprime)); isprime[0]=isprime[1]=0;for(long long i=2;i<=MAX;i++) { if(isprime[i]) {su[cnt++]=i; } for(long long j=1;j<cnt&&su[j]*i<MAX;j++) { isprime[su[j]*i]=0;} } } int main() {prime();int n,x,maxx;int i,ans = 0; while(~scanf("%d",&n) ) {ans = 0;maxx = -1;while(n--) {scanf("%d",&x);for(int i = x; i>=2; i--) {//說明是最大素因子。 if(isprime[i] && x%i==0) {if(i>maxx) {ans = x;maxx = i;}}}}ans>1?printf("%d\n",ans):printf("1\n");}return 0 ;}

AC代碼2：（0ms）

#include <cstdio> #include <cstring> const int MAXN = 20017; int s[MAXN]; int main() {int n,m;memset(s,0,sizeof(s));s[1]=1;//此題1也是素數for(int i = 2; i < MAXN; i++)//篩選所有范圍內的素數{if(s[i] == 0)//沒有被更新過for(int j = i; j < MAXN; j+=i){s[j]=i;}}while(~scanf("%d",&n)){int ans;int maxx = -1;for(int i = 0; i < n; i++){scanf("%d",&m);if(s[m] > maxx){maxx = s[m];ans = m;}}printf("%d\n",ans);}return 0; }

?

總結

以上是生活随笔為你收集整理的【POJ - 3048】Max Factor （数论，打表，水题）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。