问题描述：正整数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 之间约数个数最多的数。
数据输入：输入数据由文件名为input.txt的文本文件提供。
文件的第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 copyprint?1.#include <iostream>2.#include <fstream>3.#include <ctime>4.#include <cmath>ing namespace std;6.7.ifstream fin("input.txt");8.ofstream fout("output.txt");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 copyprint?1.#include<iostream>ing namespace std;3.#define max Max4.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.else20. {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.else65. {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* …… * Am Nm，则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）时，我们就找到了一个区间内的数，根据前面介绍的方法，可以得到它的约数个数。
所有的区间内的数的约数个数的最大值就是我们要求的目标。
为什么这种深度搜索可以减少常规枚举过程中的重复问题呢？请看下面的一个例子设给定的区间为[6,30],6,18,30为区间内的数，按照常规枚举方法，计算18,30，的时候分别计算了因子6的约数个数，重复计算2次。
如果使用上述所说的深度搜索方法，求这3个数的因数个数的路径有一条公共部分，2*3，这一部分只计算了一次，求18只需再乘个3，求30只需再乘个5，相对于常规枚举减少了两次计算2*3的时间。
但这种深度搜索也有问题，就是number有可能是无用的，下面的分析便是对这种深搜方法进行无用数据剪枝。
值得注意的是，我们枚举过程中得到的number可能无用的，即无论用number去乘以多少，都无法得到区间内的数。
这样的number如果继续枚举下去，无疑会大大降低效率。
那么，能否通过简单的判断，将其剪去呢？答案是可以的。
很容易证明，如果(min –1) div number < max div number，则区间内存在可以被number整除的数。
因为，如果区间[min, max]内存在可以被number整除的数，也即是从min到max中至少有一个数能被number整除，那么区间[min – 1, max]内的数被number除得的商肯定不止一种，所以(min – 1) div number必然小于max div number。
反过来，如果(min-1)div number=max div number,则[min,max]内不存在可以被number整除的数。