Problem Solving►UVa

UVa 10042 - Smith Numbers

Contents

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

Problem

中文網址

Solution

從 n 以上開始窮舉，每次都因式分解一邊計算每位數的總和，特別注意本身是質數的判斷。

Code

UVa 10042
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
74
75
76
77
78
79
#include<cstdio>
#define SQRTN 320
#define N 100000

bool sieve[N] = { true,true };
int prime[10000];
int getPrime()
{
    for (int i = 2; i < SQRTN; i++)
    {
        if (!sieve[i])
            for (int j = i + i; j < N; j += i)
                sieve[j] = true;
    }

    int count = 0;
    for (int i = 0; i < N; i++)
        if (!sieve[i])
            prime[count++] = i;

    return count;
}
inline int digits_sum(int n)
{
    int sum = 0;
    while (n)
    {
        sum += n % 10;
        n /= 10;
    }

    return sum;
}
int main()
{
    int P = getPrime();

    int Case;
    scanf("%d", &Case);
    while (Case--)
    {
        int ans, sum = 0, fsum = -1;
        scanf("%d", &ans);

        while (fsum != sum)
        {
            int n = ++ans, i;
            sum = digits_sum(ans);
            fsum = 0;

            if (n < N && !sieve[n])//n is prime
                continue;

            for ( i = 0; i < P&&prime[i] * prime[i] <= n; i++)
            {
                if (!(n%prime[i]))
                {
                    int ds = digits_sum(prime[i]);//因數的各位數總和
                    while (!(n%prime[i]))
                    {
                        n /= prime[i];
                        fsum += ds;
                    }
                }
            }

            if (ans == n)//ans is prime
                continue;

            if (n != 1)//n 剩下的是質數
                fsum += digits_sum(n);

        }

        printf("%d\n", ans);
    }

    return 0;
}