Posted on 2008-04-14 18:24
superman 閱讀(445)
評論(0) 編輯 收藏 引用 所屬分類:
ZOJ
1 /* Accepted 1133 C++ 00:00.04 836K */
2 #include <map>
3 #include <iostream>
4
5 using namespace std;
6
7 inline int split(int n)
8 {
9 int sum = 0;
10 while(n)
11 {
12 sum += n % 10;
13 n /= 10;
14 }
15 return sum;
16 }
17
18 inline int prime(int n) //if prime(n) == n, it's a prime number.
19 {
20 if(n % 2 == 0)
21 return 2;
22 for(int i = 3; i * i <= n; i += 2)
23 if(n % i == 0)
24 return i;
25 return n;
26 }
27
28 int main()
29 {
30 int n;
31 map <int, int> rec;
32 while((cin >> n) && n)
33 {
34 if(rec.count(n))
35 {
36 cout << rec[n] << endl;
37 continue;
38 }
39 for(int i = n + 1; true; i++)
40 {
41 if(prime(i) == i)
42 continue;
43
44 int s1 = split(i);
45
46 int s2 = 0, m = i, p;
47 while((p = prime(m)) != 1)
48 {
49 s2 += split(p);
50 m /= p;
51 }
52
53 if(s1 == s2)
54 {
55 cout << i << endl;
56 rec[n] = i;
57 break;
58 }
59 }
60 }
61
62 return 0;
63 }
64