题目：
一个数的素数因子分解是数论里面的基本问题，我们在课堂上专门讨论过这样的问题，大家也做过实验。不过今天我们要讨论的问题更加简单，只讨论某一个数的约数，假定给你任意一个数，让你找出这个数的所有约数，如6，它有1、2、3、6一共4个约数，显然这是一个非常简单的问题，但我们今天要稍微变化一下，我们请你在一定范围内找出约数最多的那个数，有点麻烦的是这个数的数值本身可能不算小。
Input 本问题有多组测试数据，对于每一组测试数据，输入只有一行，共两个正整数F，T其中1<=F<=T<=10000000。
输出有两行，第一行由三部分组成，第一部分是“[F,T]”，第二部分是区间范围内有最多约数的那个数，第三部分是约数的个数，三部分之间用一个空格隔开，行尾没有空格；第二行是对应的约数，从小到大排列，中间用一个空格隔开，末尾没有空格。当符合要求的答案不唯一时，输出有最多约数时本身数最小的那个。
Sample Input 3 10 500 550
Sample Output [3,10] 6 4 1 2 3 6 [500,550] 504 24 1 2 3 4 6 7 8 9 12 14 18 21 24 28 36 42 56 63 72 84 126 168 252 504
思路：刚看到这题的时候就想着先预处理一遍，把每个数的约数个数处理出来，但是看到这个数据范围有点慌。后来看到有人过了，只能先打一发试试，居然没有超时。。。 接下来进入正题，先是得知道约数个数怎么求，约数个数=每种质因数个数+1的乘积。比如说2的质因数为2（个数为1），所以2的约数个数为（1+1）=2；6的质因数为2（个数为1）和3（个数为1），所以6的约数个数为（1+1）（1+1）=4；12的质因数为2（个数为2）和3（个数为1），所以12的约数个数为（2+1）（1+1）=6。具体的证明什么的可以百度一下。 知道这个以后就只要求质因数和它的个数，用素数筛法可以在o（n）的时间处理约数个数的问题。 接着就是查询[F,T]这个区间内约数最多的那个。这里可以优化一下，当F小于T/2时，只要查询[T/2,T]就行了。遍历这个区间找到最大值。然后找出约数最多的数的所有约数。这里只要从1遍历到这个数的平方根就行了。这里还有一个优化，不然会超时，把找到约数的个数记录一下，如果找完了就break掉，当还未找到的约数个数为1时，剩下的这个约数就是平方跟，说明原本的数是个平方数。
下面是代码：
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<queue> #include<stack> #include<algorithm> #define N 10000005 using namespace std; bool flag[N]; int num[N],x,t,tmp; int f; queue<int> q; stack<int> s; void init() { for(int i=1;i<N;i++) num[i]=1,flag[i]=0; for(int i=2;i<N;i++) { if(flag[i]) continue; t=1; //ss.push_back(num[i]); while(t*i<N) { x=1; tmp=t*i; flag[tmp]=1; while(tmp%i==0) x++,tmp/=i; num[t*i]*=x; t++; } } } int main() { init(); /*for(int i=1;i<15;i++) printf("%d\n",num[i]);*/ while(~scanf("%d%d",&f,&t)) { printf("[%d,%d] ",f,t); f=max(f,t/2); tmp=f; x=num[f]; for(int i=f;i<=t;i++) { if(x<num[i]) { x=num[i]; tmp=i; } } printf("%d %d\n",tmp,num[tmp]); x=num[tmp]; for(int i=1;i*i<=tmp;i++) { if(x==1) { q.push((int)sqrt(tmp)); break; } if(tmp%i==0) { x-=2; q.push(i); s.push(tmp/i); } } while(!q.empty()) { printf("%d",q.front()); q.pop(); if(!q.empty()) printf(" "); } while(!s.empty()) { printf(" %d",s.top()); s.pop(); } printf("\n"); } }