【題目敘述】https://zerojudge.tw/ShowProblem?problemid=d366
【解題想法】質數表
- sqrt(1e9) = 31622.8
- 利用質數篩法找出小於sqrt(1e9)的所有質數。
- 對每個 L <= n <= U 的 n 進行質因數分解。
- n = b1^ p1 * b2 ^ p2 * b3^p3
- 則 n 有 (1+p1) * (1+p2) * (1+p3) 個因數。
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
int prime[32000];
vector <int> v;
int main() {
for (int i = 2; i < 32000; i++){
if (prime[i] == 0){
v.push_back(i);
for (int j = 2*i; j < 32000; j+=i){
prime[j] = 1;
}
}
}
int T, L, U;
cin >> T;
while (T--){
cin >> L >> U;
int mx = 0, idx = 0;
for (int i = L; i <= U; i++){
int n = i, cnt = 1;
for (auto b: v){
int p = 0;
while (n % b == 0){
p++;
n /= b;
}
cnt *= (p+1);
if (n == 1) break;
}
if (cnt > mx){
mx = cnt;
idx = i;
}
}
cout << "Between " << L << " and " << U << ", " << idx << " has a maximum of " << mx << " divisors.\n";
}
return 0;
}