问题描述：
正整数x的约数是能整除x的正整数。正整数x 的约数个数记为div(x)。例如，1，2，5，10 都是正整数10 的约数，且div(10)=4。设a 和b 是2 个正整数，a≤b，出a和b之间约数个数最多的数x。
编程任务：
对于给定的2个正整数a≤b，编程计算a 和 b 之间约数个数最多的数。
数据输入：
输入数据由文件名为的文本文件提供。文件的第1 行有2 个正整数 a和 b。
结果输出:
程序运行结束时，到a 和b之间约数个数最多的那个数及最多约数个数。
测试数据：【只给出最多约数个数, time limit: 1s】
[1, 36] 9
[1000000, 2000000] 288
[999998999, 999999999] 1024
[1, 1000000000] 1344
[999999999, 1000000000] 56
[100, 1000000000] 1344
———————————————————————————————————————————————————
法一：主要就是查一个整数的约数个数的效率问题，首先想到的是 1-√x 遍历。逐个判断。但是效率太低。
[cpp] view plain copy
print?
1.#include <iostream>
2.#include <fstream>
3.#include <ctime>
4.#include <cmath>
5.using namespace std;
6.
7.ifstream fin("");
8.ofstream fout("");
9.
10.clock_t start,finish;
11.double total_time;
12.
13.int div(int n)
14.{
15. int num = 0;
16. for (int i = 1; i < sqrt((float)n); i++)
17. {
18. if (n%i == 0)
19. {
20. num += 2;
21. }
22.
23. }
24.
25. if (n == (int)sqrt((float)n)*(int)sqrt((float)n))
26. {
27. num ++;
28. }
29. return num;
30.}
31.
32.int caculateMaxdiv(int a, int b)
33.{
34. int maxNum = 0;
35. for (int i = a;i <= b;i++ )
36. {
37. if ( maxNum < div(i))
38. {
39. maxNum = div(i);
40. }
41. }
42. return maxNum;
43.}
44.
45.int main()
46.{
47. start = clock();
48. int a,b;
49. fin>>a>>b;
50. fout<<caculateMaxdiv(a,b)<<endl;
51. finish = clock();
52.
53. total_time = (double)(finish - start)/CLOCKS_PER_SEC;
54. fout<<total_time<<" s"<<endl;
55. return 0;
56.}
法二：
思想：设正整数x的质因子分解为
x＝p1^N1 × p2^N2 ×……pi^Ni
则 div（x）＝(N1＋1)(N2＋1)……(Ni＋1)
[cpp] view plain copy
print?
1.#include<iostream>
2.using namespace std;
3.#define max Max
4.const long MAXP = 100000;
5.long prim[MAXP];
6.long max, numb, PCOUNT; //max存放最多约数个数，numb存放约数个数最多的数
7.void primes(); //用筛选法产生质数存于prim数组中
8.void search(long from, long tot, long num, long low, long up);
9.int main()
10.{
11. primes();
12. long l, u;
13. cin >> l >> u;
14. if ((l == 1) && (u == 1))
15. {
16. max = 1;
17. numb = 1;
18. }
19. else
20. {
21. max = 2;
22. numb = l;
23. search(1, 1, 1, l, u);
24. }
25. cout << max << endl << numb << endl;
26. system("pause");
字符串长度最大是多少27. return 0;
28.}
29.
30.void primes()
31.{
32. bool get[MAXP+1];
33. long i;
34. for (i = 2; i <= MAXP; i++)
35. get[i] = true;
36. for (i = 2; i <= MAXP; i++)
37. if (get[i])
38. {
39. long j = i + i;
40. while (j <= MAXP)
41. {
42. get[j] = false;
43. j += i;
44. }
45. }
46. long ii, j;
47. for (ii = 2, j = 0; ii <= MAXP; ii++)
48. if (get[ii]) prim[++j] = ii;
49. PCOUNT = j;
50.}
51.
52.void search(long from, long tot, long num, long low, long up)
53.{
54. if (num >= 1)
55. if ( (tot > max) || ((tot == max) && (num < numb)) )
56. {
57. max = tot;
58. numb = num;
59. }
60. if ((low == up) && (low > num)) search(from, tot*2, num*low, 1, 1);
61. for (long i = from; i <=PCOUNT; i++)
62. {
63. if (prim[i] > up) return;
64. else
65. {
66. long j = prim[i], x = low - 1, y = up, n = num, t = tot, m = 1;
67. while (true)
68. {
69. m++;
70. t += tot;
71. x /= j;
72. y /= j;
73. if (x == y) break;
74. n *= j;
75. search(i+1, t, n, x+1, y);
76. }
77. m = 1 << m;
78. if (tot < max / m) return;
79. }
80. }
81.}
针对此方法的解析如下（源自网络）：
本题的要求是，求出一个给定区间内的含约数最多的整数。
首先明确一下如何求一个数的约数个数：若一个数N满足：N = A1N1 * A2N2 * A3N3 * …… * AmNm，则n的约数个数为(N1 + 1) (N2 + 1) (N3 + 1) …… (Nm + 1)。这是可以用乘法原理证明的。
最浅显的算法是，枚举区间内的每个整数，统计它们的约数个数。这个算法很容易实现，但是时间复杂度却相当高。因为题目约定区间的最大宽度可以达到10^9的数量级，相当庞大。因此，在极限规模时，时间是无法忍受的。所以，我们需要尽量的优化时间。
分析一下枚举的过程就会发现，如果我们枚举到两个数n和m*n（m为一相对于n较大的质数），那么我们将重复计算n的约数两次。据此，我们发现了枚举效率低的根本所在。为了解决这一重复，我们可以选取另一种搜索方法——以质因子为对象进行深度搜索。
初始时，令number := 1，然后从最小的质数2开始枚举，枚举包含一个2、两个2……n个2
的情况……直至number * 2n大于区间的上限（max）。对于每种“2^k的情况”，令number := number * 2n，再枚举3的情况，然后，枚举5的情况、7的情况……方法相同。整个过程是一个深度搜索的过程。当number大于等于区间下限（min）时，我们就到了一个区间内的数，根据前面介绍的方法，可以得到它的约数个数。所有的区间内的数的约数个数的最大值就是我们要求的目标。
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论