AOJ 2048 - Everlasting...?

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2048

概要

正の整数 n の key number を「a の最大の素因数から，他の素因数の和を引いたもの」と定義する．

2つの正の整数 a, b が与えられるので，どちらの key number が大きいかどうかを答える．

制約

• 2 <= a, b <= 10^6
• a と b の key number が等しくなることはない

解法

やるだけ．10^6 程度なので，素数表を作ったりする必要も無い．

 1 #include <iostream>
 2 using namespace std;
 3 
 4 int key(int x)
 5 {
 6   int s = 0, m = 0;
 7   for (int i = 2; i <= x; i++) {
 8     if (x % i == 0) {
 9       s += i;
10       m = i;
11       while (x % i == 0) {
12         x /= i;
13       }
14     }
15   }
16   return m - (s-m);
17 }
18 
19 int main()
20 {
21   int a, b;
22   while (cin >> a >> b && a != 0) {
23     cout << (key(a) > key(b) ? 'a' : 'b') << endl;
24   }
25   return 0;
26 }