UVa 294 - Divisors

题目：计算一个给定区间中因数最多的数。

分析：数论、组合数学。题目的数据的比较大，如果暴力一定会超时，那么就考虑利用其他方法求解。

我们将给定数字因式分解，那么因数的个数就是π(各质因子数+1)。（每个质因子取0~上限个）

因为数据时在10^9之内，所以质因数只能是33333以内的素数，利用筛法将素数打表计算即可。

#include <iostream>  
#include <cstdlib>  
  
using namespace std;  
  
int visit[34000];  
int prime[34000];  
  
//因式分解，计算因子个数   
int number( int a, int n )  
{  
    int sum = 1;  
    for ( int i = 0 ; a > 1 && i < n ; ++ i )   
        if ( a%prime[i] == 0 ) {  
            int count = 1;  
            while ( a%prime[i] == 0 ) {  
                count ++;  
                a /= prime[i];  
            }  
            sum *= count;  
        }  
    return sum;  
}  
  
int main()  
{  
    //利用筛法计算素数，打表   
    for ( int i = 0 ; i < 34000 ; ++ i )  
        visit[i] = 1;  
    int count = 0;  
    for ( int i = 2 ; i < 34000 ; ++ i )  
        if ( visit[i] ) {  
            prime[count ++] = i;  
            for ( int j = 2*i ; j < 34000 ; j += i )  
                visit[j] = 0;  
        }  
      
    long a,b,c;  
    while ( cin >> c )  
    while ( c -- ) {  
        cin >> a >> b;  
        long save = a,max = 0,temp;  
        for ( long i = a ; i <= b ; ++ i ) {  
            temp = number( i, count );  
            if ( temp > max ) {  
                max = temp;  
                save = i;  
            }  
        }  
          
        cout << "Between " << a << " and " << b << ", " << save  
             << " has a maximum of " << max << " divisors.\n";  
    }  
    return 0;  
}

补充：软件开发 , C++ ,