hdu 2710 Max Factor（找最大素数）

时间：2014-08-21 00:18:23 收藏：0 阅读：341

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2710

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 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

Sample Output

Source

USACO 2005 October Bronze

题意：
求给出数据含有最大质数的数，如：36 38 40 42 即19为38的最大质数，也是4个数中最大的质数。

所以输出包含最大质数的数38，还要题目最后说如果有多个，要输出最前面的那个数。

思路：

先打表出所有的素数，然后再寻找即可！

代码如下：

#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;
}

hdu 2710 Max Factor（找最大素数）,布布扣,bubuko.com

原文：http://blog.csdn.net/u012860063/article/details/38715373