K_程式人

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=230

#include <cstdio>
#include <iostream>
using namespace std;
int prime[1000], num = 0;

int main() {
    for (int i = 2; i < 1500; i++){
        bool flag = false;
        for (int j = 2; j*j <= i; j++)
            if(i%j == 0) {
                  flag = true;
                break;
            }

        if (!flag)
            prime[num++] = i;
    }

    int N, L, U;
    cin >> N;
    while (N--){
        cin >> L >> U;
        int Max = 0, maxNum;

        for (int i = L; i <= U; i++){
            int sum = i, ans = 1;
            for(int j = 0; j < num && sum > 1; j++){
                int pow = 1;
                while (sum % prime[j] == 0){
                    pow++;
                    sum /= prime[j];
                }
                ans *= pow;
            }
            if (ans > Max)
                Max = ans, maxNum = i;
        }
        cout << "Between " << L << " and " << U << ", " << maxNum << " has a maximum of " << Max << " divisors." << endl;
    }

    return 0;
}