HDOJ/HDU 2710 Max Factor(素数快速筛选~)
发布日期:2021-06-29 13:35:44
浏览次数:2
分类:技术文章
本文共 1814 字,大约阅读时间需要 6 分钟。
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 42Sample Output
38哎~又一个英文题~
题意:
输入一个正整数n,然后输入n个正整数(1<=a[i]<=20000),要你求这n个数里哪个数的最大素因数(即能被该数整除(包括这个数本身!)的最大素数)最大,然后输出这个数。若有两个数的最大素因数相同,则输出前面那个。用到了素数快速筛选~不然会超时的~
import java.util.Arrays;import java.util.Scanner;/** * @author 陈浩翔 */public class Main{ static boolean db[] = new boolean[20005]; public static void main(String[] args) { dabiao(); Scanner sc = new Scanner(System.in); while(sc.hasNext()){ int n = sc.nextInt(); int a[] = new int[n]; int prime[] = new int[n]; for(int i=0;imax){ max=prime[i]; con=i; } } System.out.println(a[con]); } } private static void dabiao() { Arrays.fill(db, true); for(int i=2;i<=Math.sqrt( db.length);i++){ for(int j=i+i;j
转载地址:https://chenhx.blog.csdn.net/article/details/51449644 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过按个爪印,很不错,赞一个!
[***.219.124.196]2024年04月16日 23时14分08秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
推荐算法:基于物品的协同过滤算法
2019-04-29
docker系列3:docker搭建CDH集群[单机单节点]
2019-04-29
ubuntu 16:使用系统自带的中文输入法
2019-04-29
k8s单机版[ microk8s ]
2019-04-29
docker系列6 :k8s集群[ 解压安装 ]
2019-04-29
maven- idea: 打包可执行jar
2019-04-29
docker系列2: windows安装docker
2019-04-29
hbase数据转移: 导入导出
2019-04-29
docker系列7: docker搭建mysql
2019-04-29
windows server 2012设置远程连接断开后自动注销
2019-04-29
python基础:list,map,open()文件读写
2019-04-29
Go面向对象-接口
2019-04-29
Go-多路选择和超时控制
2019-04-29
Go-channel的关闭和广播
2019-04-29
Go-任务的取消
2019-04-29
AIX 作为Web Server 使用时,tcp相关的几个参数调整
2019-04-29
自我学习37:请描述一下网页从开始请求到最后展示的完整过程
2019-04-29
自我学习38:如何区分前后端BUG
2019-04-29
自我学习39:接口自动化测试用例&功能测试用例区别
2019-04-29
mirror去兔子补丁下载 附安装教程
2019-04-29