给出一个区间，问其中哪个数因子最多。对每个数进行唯一分解，然后求出素因子乘积即为因子个数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include <cstdio>
using namespace std;
const int maxn = 34000;
int prime[maxn],p;
bool np[maxn]={true,true};
void pre() {
for(int i = 2; i < maxn; ++i) {
if(!np[i]) prime[p++] = i;
for(int j = 0; j < p && i * prime[j] < maxn; ++j) {
np[i * prime[j]] = true;
if(!(i % prime[j])) break;
}
}
return;
}
int solve(int n) {
int cur = 1;
for(int i = 0; i < p; ++i) {
int cnt=1;
if(n % prime[i] == 0) {
while(n % prime[i] == 0 && n)
n /= prime[i], ++cnt;
cur *= cnt;
}
}
return cur;
}
int main() {
pre();
int t; scanf("%d", &t);
while(t--) {
int l, r; scanf("%d%d", &l, &r);
int max_n = 0, ans = l;
for(int i = l; i <= r; ++i) {
int k=solve(i);
if(k > max_n) max_n = k,ans =i;
}
printf("Between %d and %d, %d has a maximum of %d divisors.\n", l, r, ans, max_n);
}
return 0;
}
|
** 本文迁移自我的CSDN博客，格式可能有所偏差。 **