Problem Solving►UVa

UVa 294 - Divisors

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

中文網址

Solution

直接因數分解找出有幾個因數即可。

Code

UVa 294
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<cstdio>
#include<cmath>
#define N 100000
#define M 50000

int prime[M];
bool sieve[N]{ true, true };

inline void getPrime();
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 getPrime()
{
    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;
    }
}