Uva 294 Divisors(唯一分解定理)

题意：求区间内正约数最大的数。

原理：唯一分解定义（又称算术基本定理），定义如下：

　　任何一个大于1的自然数，都可以唯一分解成有限个质数的乘积，这里均为质数，其诸指数是正整数。这样的分解称为

的标准分解式。（取自百度百科）

根据原理，正约数数量 = (1+a1)(1+a2)..(1+an)

因此我们需要先求出所有素数，进而求出a1,a2,..an的大小。

原题给的数字范围是1<=L<=U<=10^9,假如要全部算一遍需要很长时间。那么可能最大的正约数是多少呢？

回想我们所用的判断素数的算法（第五行到第十二行），最大可能的正约数不会超过根号n。求得n大约是31622。

然后我们就可以把1<=n<=31622内的素数打表来加速我们的计算。

完整代码如下：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 vector<int> prime;
 4 //31622
 5 int is_prime(int n)
 6 {
 7     int k = floor(sqrt(n)+0.5);
 8     for(int i = 2; i <= k; i++){
 9         if(n%i==0)return 0;
10     }
11     return 1;
12 }
13 int divinum(int n){
14     int sum = 1;
15     unsigned k = 0;
16     while(n>1&&k<prime.size()){
17         int  t = 1;
18         while(n%prime[k]==0){
19             n/=prime[k];
20             t++;
21         }
22         k++;
23         sum*=t;
24     }
25     return sum;
26 }
27 int main(){
28     int n;
29     for(int i = 2; i <= 31622; i++){
30         if(is_prime(i))
31             prime.push_back(i);
32     }
33     cin >> n;
34     while(n--){
35         int L, U;
36         cin >> L >> U;
37         int max_factor = 0;
38         max_factor = 0;
39         int max_num = 0;
40         for(int i = L; i <= U; i++){
41             int k = divinum(i);
42             if(k > max_factor){
43                 max_factor = k;
44                 max_num =i;
45             }
46         }
47         printf("Between %d and %d, %d has a maximum of %d divisors.
",L,U,max_num,max_factor);
48     }
49     return 0;
50 }