Problem Description 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 lineOutput
* 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
436384042 Sample Output 38 这题需要用到筛法，不然容易超时！所谓筛法其原理为：素数的倍数一定不是素数！
具体做法是：先把N个自然数按次序排列起来。1不是质数，也不是合数，要划去。第二个数2是质数留下来，而把2后面所有能被2整除的数都划去。2后面第一个没划去的数是3，把3留下，再把3后面所有能被3整除的数都划去。3后面第一个没划去的数是5，把5留下，再把5后面所有能被5整除的数都划去。这样一直做下去，就会把不超过N的全部合数都筛掉，留下的就是不超过N的全部质数。
下面是求1—N之间所有的素数的模版（LRJ优化版）！
void prime() { int m=(int)sqrt(N+0.5); memset(vis,false,sizeof(vis)); for(int i=2;i<=m;i++) { if(!vis[i]) { for(int j=i*i;j<=N;j+=i) vis[j]=true; } } }
对于这道题，我们先打表求出20000以内的所有的素数，然后每输入一个数，求其最大的素因子，具体问题见代码：
#include<cstdio> #include<cmath> #include<algorithm> using namespace std; #define N 20000+10 bool vis[N]; void prime() { int m=(int)sqrt(N+0.5); memset(vis,false,sizeof(vis)); for(int i=2;i<=m;i++) { if(!vis[i]) { for(int j=i*i;j<=N;j+=i) vis[j]=true; } } } int max_prime(int x)//求x的最大素数因子 { for(int i=x;i>=1;i--) if(!vis[i] && x%i==0) return i; } int main() { freopen("input.in","r",stdin); freopen("output.out","w",stdout); int num,temp,mm,arr[N],maxn; prime(); while(scanf("%d",&num)!=EOF && num) { maxn=0; for(int i=0;i<num;i++) { scanf("%d",&arr[i]); temp=max_prime(arr[i]); if(maxn<temp) { maxn=temp; mm=i; } } printf("%d/n",arr[mm]); } return 0; }
