抓其根本(hdu2710 Max Factor 素数 最大公约数 最小公倍数…..) – 若忆_star

素数判断:

一、根据素数定义,该数除了1和它本身以外不再有其他的因数。

详见代码。

1 int prime()
2 {
3 for (int i=2; i*i<=n; i++)
4 {
5 if (n%i==0) //不是素数
6 return 1; //返回1
7 }
8 return 0; //是素数返回0
9 }

二、打表,将所有的素数一一列出,存在一个数组里。

详见代码。

1 void prime()
2 {
3 for (int i=2; i<20050; i++) //从2开始一个一个找
4 {
5 if (hash[i]==0) //这一个判断可以减少很多重复的,节省很多时间
6 {
7 for (int j=2; i*j<20050; j++) //只要乘以i就一定不是素数
8 {
9 hash[i*j]=1; //不是素数标记为1
10 }
11 }
12 }
13 }

举个例子:hdu2710 Max Factor

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

Max Factor

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

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
 

题目大意:找到所给数的最大素因子,然后在比较这些素因子的大小,找到最大的,最后输出原有的那个数。

 

详见代码。

1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4
5 using namespace std;
6
7 int hash[20050];
8
9 void prime()
10 {
11 for (int i=2; i<20050; i++)
12 {
13 if (hash[i]==0)
14 {
15 for (int j=1; i*j<20050; j++)
16 {
17 hash[i*j]=i;//i表示的是最大的素因子
18 }
19 }
20 }
21 //return hash[n];
22 }
23
24 int main ()
25 {
26 int T;
27 memset(hash,0,sizeof(hash));
28 sushu();
29 while (~scanf(%d,&T))
30 {
31 int Max=0,x=1;
32 while (T–)
33 {
34 int n;
35 scanf(%d,&n);
36 if (hash[n]>Max)
37 {
38 Max=hash[n];
39 x=n;
40 }
41 }
42 printf (%dn,x);
43 }
44 return 0;
45 }

 

最大公约数(gcd)

详见代码。

1 int gcd(int a,int b)
2 {
3 return a%b?gcd(b,a%b):b;
4 }

最小公倍数

求解最小公倍数,一般都要借助最大公约数。辗转相除求得最大公约数,再用两数之积除以此最大公约数,得最小公倍数。

 

注意基本!!!

本文链接:抓其根本(hdu2710 Max Factor 素数 最大公约数 最小公倍数…..),转载请注明。



You must enable javascript to see captcha here!

Copyright © All Rights Reserved · Green Hope Theme by Sivan & schiy · Proudly powered by WordPress

无觅相关文章插件,快速提升流量