HDOJ 2710 Max Factor (筛素法求最大因子)_hdoj 2710 max factor-程序员宅基地

技术标签: 数论  素数  

Max Factor

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5557    Accepted Submission(s): 1799


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
  
  
   
4 36 38 40 42
 

Sample Output
38

题意:给你n个数,求素因子最大的那个数,如果素因子大小相同,结果为最小的那个数
思路:在素数筛选过程中,用一个数组存储每个数的最大因子,因为因子为素数,所以说最后一个乘积所用的i是乘积数最大因子,然后过程比较就行了

ac代码:
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define INF 0xfffffff
using namespace std;
int v[1000100];
int ans[1000100];
void db()
{
	memset(v,0,sizeof(v));
	v[1]=1;
	for(int i=2;i<1000100;i++)
	{
		if(!v[i])
		{
			ans[i]=i;
			for(int j=i*2;j<1000100;j+=i)
			ans[j]=i,v[j]=1;
		}
	}
}
int main()
{
	db();
	int n,a,i;
	while(scanf("%d",&n)!=EOF)
	{
		int M=-INF;
		int Ans=-INF;
		for(i=0;i<n;i++)
		{
			scanf("%d",&a);
			if(ans[a]>M)
			{
				M=ans[a];
				Ans=a;
			}
			else if(ans[a]==M)
			{
				if(a>Ans)
				Ans=a;
			}
		}
		printf("%d\n",Ans);
	}
	return 0;
}





 
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/helloiamclh/article/details/50533696

智能推荐

js 导出excel表格时身份证或数字过长会出现科学计数法_js 导出身份证号码显示e+17-程序员宅基地

文章浏览阅读1k次。问题描述:js在导出excel表格时身份证或数字过长会出现科学计数法,如E+13等。_js 导出身份证号码显示e+17

excel函数讲解-程序员宅基地

文章浏览阅读331次,点赞9次,收藏10次。插入一列快捷键:Ctrl+Shift+“+”

Python绘制一个简单的圣诞树-程序员宅基地

文章浏览阅读1.8k次,点赞9次,收藏9次。在Python中,你可以使用基本的打印语句和循环来绘制一个简单的圣诞树。每一行的空格数量会随着行号逐渐减少,而星号的数量则逐渐增加,形成圣诞树的形状。如果你想要一个更复杂的圣诞树,比如带有装饰和树干的,你可能需要使用一些图形库,比如。这个函数会打印出一个由星号(*)组成的圣诞树,树的高度由参数。但是,这需要更复杂的代码和更多的设置。

执行webpack -v,CLI for webpack must be installed.webpack-cli (https://github.com/webpack/webpack-cli)_运行webpack -v 报错cli for webpack must be installed. -程序员宅基地

文章浏览阅读381次。执行webpack -v,却没返回版本消息PS E:\mango-ui> webpack -v ,CLI for webpack must be installed.webpack-cli (https://github.com/webpack/webpack-cli) We will use "npm" to install the CLI via "npm install -D webpack-cli".Do you want to install 'webpack-cli' (yes/no): _运行webpack -v 报错cli for webpack must be installed. webpack-cli

js手写题——高阶函数&函数柯里化&compose函数&ES6装饰器_js 装饰器和高阶函数-程序员宅基地

文章浏览阅读225次。高阶函数以函数作为参数/以函数作为返回值/常用于作为函数装饰器常用高阶函数:防抖Debounce和节流Throttlejs手写题——防抖和节流 Promise、setTimeout等等为什么要使用高阶函数?减少非纯函数的数量,增加系统稳定性与可靠性,纯函数方便做单元测试。函数柯里化函数式编程思想,既能减少代码冗余,也能增加可读性。它利用高阶函数,通过函数调用继续返回函数的形式,将接收多个参数转换为多次接收参数最后统一处理。理解函数柯里化function curry(fn,currArgs){_js 装饰器和高阶函数

数据库的索引_稠密索引和稀疏索引的区别-程序员宅基地

文章浏览阅读348次。(一)顺序索引1. 聚集索引(主索引)和非聚集索引(辅助索引)(1)聚集索引:包含记录的文件按照某个搜索码的顺序排序。(2)非聚集索引:搜索码制定的顺序与文件中记录的物理顺序不同(搜索码不是候选码)。 2. 稠密索引和稀疏索引(1)稠密索引:文件中的每个搜索码值都有一个索引项。在稠密聚集索引中,索引项包括搜索码值以及指向具有该搜索码值的第一条数据记录的指针;在稠密非..._稠密索引和稀疏索引的区别

随便推点

使用Mecanim动画系统来控制2D动画_2d动画重定向-程序员宅基地

文章浏览阅读1.4k次。使用Mecanim动画系统来控制2D动画原文:http://qinyuanpei.com/2015/02/11/unity2d-game-development-mecanim/今天我想和大家分享的话题是在Unity3D中使用Mecanim动画系统来控制2D动画。相信在大家的印象中,Mecanim动画系统主要运用在3D动画中,因为Mecanim动画系统提供了像动画重_2d动画重定向

树莓派接入USB摄像头并使用fswebcam和mjpg-streamer进行测试_在树莓派ros2中安装usb摄像头驱动-程序员宅基地

文章浏览阅读983次,点赞28次,收藏31次。在我之前的博文里,将USB摄像头接入了香橙派并实现了垃圾类型识别;现在尝试将相同的USB摄像头接入树莓派!并测试拍照,视频流等功能,最后实现mjpg-streamer的开机自启功能!_在树莓派ros2中安装usb摄像头驱动

Python 之12306网站验证码校验案例-程序员宅基地

文章浏览阅读5次。import requestsfrom PIL import Imageimport jsonsrequests.packages.urllib3.disable_warnings()headers = { "User-Agent": 'Mozilla/5.0 (Windows NT 10.0; WOW64) AppleWebKit/537.36 (KHTML, like ..._12306验证 python

Vue面试相关问题_error with push/replace state domexception: failed-程序员宅基地

文章浏览阅读433次。1、vue解决了什么问题解决了用 DOM API 操作 UI 过于反人类的问题。React 通过 UI = f(data) 解决。Vue 通过 Reactive 响应式数据解决。更多关于上述问题理解2、MVVM的理解MVVM分为Model、View、ViewModel三者。Model:代表数据模型,数据和业务逻辑都在Model层中定义;View:代表UI视图,负责数据的展示;ViewModel:就是与界面(view)对应的Model。因为,数据库结构往往是不能直接跟界面控件一一对应上的_error with push/replace state domexception: failed to execute 'pushstate' on

使用自有数据集微调ChatGLM2-6B_chatglm微调自己的数据集-程序员宅基地

文章浏览阅读1.9k次,点赞38次,收藏32次。P-Tuning v2的原理是通过对已训练好的大型语言模型进行参数剪枝,得到一个更加小巧、效率更高的轻量级模型。具体地,P-Tuning v2首先使用一种自适应的剪枝策略,对大型语言模型中的参数进行裁剪,去除其中不必要的冗余参数。然后,对于被剪枝的参数,P-Tuning v2使用了一种特殊的压缩方法,能够更加有效地压缩参数大小,并显著减少模型微调的总参数量。_chatglm微调自己的数据集

GNU gettext utilities-程序员宅基地

文章浏览阅读3.4k次。Table of Contents1 Introduction1.1 The Purpose of GNUgettext1.2 I18n, L10n, and Such1.3 Aspects in Native Language Support1.4 Files Conveying Translations1.5 Overview of GNUgettext2 Th_gnu gettext utilities

推荐文章

热门文章

相关标签