Max Factor（技巧题）-白红宇的个人博客

Max Factor（技巧题）

发布日期：2021-10-16 05:05:11 浏览次数：47 分类：技术文章

本文共 1788 字，大约阅读时间需要 5 分钟。

Max Factor

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 6649		Accepted: 2609

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

436384042

Sample Output

Hint

OUTPUT DETAILS:

19 is a prime factor of 38. No other input number has a larger prime factor.

Source

题意：

从一串数字中找到有最大素数因子的数输出。

思路：

在判断是否为素数时，改变，用点小技巧，另不是素数的等于他的一个最大的素数因子。

代码：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;int a[20055];int maxx,num;int main(){    int n,m;    memset(a,0,sizeof(a));    a[1]=1;    for(int i=2; i<20055;i++)    {        if(a[i]==0)            for(int j=i;j<20055;j+=i)            {                a[j]=i;  //关键点            }    }    while(~scanf("%d",&n))    {        maxx=-1;        for(int i=0;i
       
        maxx)            {                maxx=a[m];                num=m;            }        }        printf("%d\n",num);    }    return 0;}

转载地址：https://blog.csdn.net/sinat_37668729/article/details/77071031 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：Hopscotch（dfs）

下一篇：Satellite Photographs（dfs）

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章