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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
|
#include<cmath>
#define N 100000
#define M 50000
int prime[M];
bool sieve[N]{ true, true };
inline void ();
int main()
{
getPrime();
int Case;
scanf("%d", &Case);
while (Case--)
{
int a, b;
int max = 0, max_count = 0;
scanf("%d%d", &a, &b);
for (int i = a; i <= b; i++)
{
int total = 1, temp = i;
for (int j = 0; prime[j] && prime[j] * prime[j] <= temp; j++)
{
int count(0);
while (!(temp%prime[j]))
{
temp /= prime[j];
count++;
}
total *= (count + 1);
}
if (temp != 1)
total <<= 1;
if (total > max_count)
{
max_count = total;
max = i;
}
}
printf("Between %d and %d, %d has a maximum of %d divisors.n", a, b, max, max_count);
}
return 0;
}
inline void ()
{
int _sqrt = sqrt(N - 1);
for (int i = 2; i < _sqrt; i++)
{
if (!sieve[i])
for (int k = (N - 1) / i; k >= i; k--)
if (!sieve[k])
sieve[k*i] = true;
}
int count(0);
for (int i = 0; i < N; i++)
{
if (!sieve[i])
prime[count++] = i;
}
}
|
近期评论