SCAU2020春季个人排位赛div2 #2--H

左手的ㄟ右手 2023-07-07 12:39 38阅读 0赞

## 简单说下 ##

这个题目的大意是农场主给每个牛编号了，含有最大素数因子的编号的奶牛地位最大，题目让我们找出最大的素数因子对应的编号。  
所以这题该怎么写呢？？  
首先我们先要打一个比给定范围大一丢丢的素数因子表。  
有人或许会问，这个素数因子表咋打啊？？  
其实就是在打素数筛表的基础上稍微改动，下面举个例子。  
比如说开始打表的时候，我是从2开始的，2的素数因子是其本身这不用说，然后将2的倍数的那些数对应的因子都置为2，后面循环不断更新。  
其实就是把本来属于素数筛表倍数的那些要变为true的数换成了对应的素数因子而已。  
然后表打完了以后，就很容易做了。  
我们定一个变量max，一个记录的变量ans，我们每次循环更新max，直到最后输出最大的max对应对应的ans，就是答案了。

题目如下：  
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

代码如下：

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<string>
    using namespace std;
    #define ll long long
    int sb[20030]= {
        0};
    int main()
    {
        
        int CASE,cow;
        sb[1]=1;
        for(int i=2; i<20030; i++)
        {
        
            if(sb[i] == 0)
                for(int j=i; j<20030; j=j+i)
                {
        
                    sb[j]=i;
                }
        }
        while(cin>>cow)
        {
        
            int ans,n,max1=-1;
            for(int i=0; i<cow; i++)
            {
        
                cin>>n;
                if(sb[n]>max1)
                {
        
                    max1=sb[n];
                    ans=n;
                }
            }
            cout<<ans<<endl;
        }
        return 0;
    }