【題目敘述】https://zerojudge.tw/ShowProblem?problemid=e629 (考生答對率: 38.27%)
【解題想法】
- 找出因數和等於S的最大整數。
- 從 S – 1 開始向下枚舉每一個整數 N，如果 N 的所有因數和等於 S，N即為答案。
- N 的所有因數和，從 1 <= p <= sqrt(N)，若 p 為 N 的因數，則必存在一數 q 為 N 的因數，且 p * q = N。
- 當 p = q = sqrt(N)，p 和 q 為相同的數，不重複加總。
#include <iostream>
#include <cmath>
using namespace std;
int main() {
int S, Case = 1;
while (cin >> S){
if (S == 0) break;
cout << "Case " << Case++ << ": ";
if (S == 1){
cout << "1\n";
continue;
}
int ans = -1;
for (int i = S-1; i >= 1; i--){
int sum = 0;
for (int j = 1; j <= sqrt(i); j++){
if (i % j == 0){
sum += j;
if (j * j != i) sum+= i/j;
}
}
if (sum == S){
ans = i;
break;
}
}
cout << ans << "\n";
}
return 0;
}
Python code (credit: Amy Chou)
Case = 1
while True:
S = int(input())
if S == 0:
break
print(f"Case {Case}: ", end="")
Case += 1
if S == 1:
print(1)
continue
ans = -1
for i in range(S-1, 0, -1):
Sum = 0
for j in range(1, int(i**0.5)+1):
if i % j == 0:
Sum += j
if j*j != i:
Sum += i // j
if Sum == S:
ans = i
break
print(ans)