Uva294 Divisors

题目：

Mathematicians love all sorts of odd properties of numbers. For instance, they consider 945 to be an interesting number, since it is the first odd number for which the sum of its divisors is larger than thenumber itself.
To help them search for interesting numbers, you are to write a program that scans a range of numbers and determines the number that has the largest number of divisors in the range. Unfortunately, the size of the numbers, and the size of the range is such that a too simple-minded approach may take too much time to run. So make sure that your algorithm is clever enough to cope with the largest possible range in just a few seconds.
Input
The first line of input specifies the number N of ranges, and each of the N following lines contains a
range, consisting of a lower bound L and an upper bound U, where L and U are included in the range.
L and U are chosen such that 1 ≤ L ≤ U ≤ 1000000000 and 0 ≤ U − L ≤ 10000.
Output
For each range, find the number P which has the largest number of divisors (if several numbers tie for
first place, select the lowest), and the number of positive divisors D of P (where P is included as a
divisor). Print the text ‘Between L and H, P has a maximum of D divisors.’, where L, H, P,
and D are the numbers as defined above.
Sample Input
3
1 10
1000 1000
999999900 1000000000
Sample Output
Between 1 and 10, 6 has a maximum of 4 divisors.
Between 1000 and 1000, 1000 has a maximum of 16 divisors.
Between 999999900 and 1000000000, 999999924 has a maximum of 192 divisors.

题意：
输入两个整数L, U，统计区间[L, U]的整数中哪一个的正约数最多。如果有多个，输出最小值。

由于数据很大，因此此题不能使用暴力。因此这道题可以用数论的知识。
正整数n的唯一分解式n = p1^a1 * p2^a2 * p3^a3 * ... * pk^ak，则n的正约数的个数为: (a1 + 1) * (a2 + 1) * ... * (ak + 1)（n的任意正约数也只能包含p1，p2，p3等素因子）。

参考代码：

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 34000;

int primes[N];
int tot = 0;

void isprimes() {
    for (int i = 2;i < N;++i) {
        if (!primes[i]) primes[tot++] = i;
        for (int j = i * 2;j < N;j += i) {
            primes[j] = 1;
        }
    }
    //cout << tot << endl;
}

int fenjie(LL n) {
    int ans = 1;
    int n1 = n;
    for (int i = 0;n > 1 && i < tot;++i) {
        if (n % primes[i] == 0) {
            int ai = 1;//被分解的数可以包含多少个当前的素数;
            while (n % primes[i] == 0) {
                ++ai;
                n = n / primes[i];
            }
            ans *= ai;      
        }
    }
    return ans;
}

void judge(LL a, LL b) {
    int maxnum = 0;
    LL loc = 0;
    for (LL num = a;num <= b;++num) {
        int yueshu = fenjie(num);
        if (yueshu > maxnum) {
            maxnum = yueshu;//找到最大正约数的个数;
            loc = num;//找到满足条件的最小的数;
        }
    }
    cout << "Between " << a << " and " << b << ", " << loc << " has a maximum of " << maxnum << " divisors." << endl;  
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    isprimes();
    //cout << primes[tot-1] << " "; cout << endl;
    int t;
    cin >> t;
    LL a, b;
    while (t--) {
        cin >> a >> b;
        judge(a, b);
    }
    return 0;
}