Largest-Prime-Factor Sequence
National Olympiad — National round (2021 season)
Submission name: seq.cpp
Problem summary
A sequence starts at 2. Each next term equals the preceding term plus its largest prime divisor. Find the N-th term.
Input
One integer N.
Output
The N-th sequence term.
Constraints
1 ≤ N ≤ 80,000.
Worked example
An independently prepared example for this explanation.
Input
10
Output
35
Solution analysis
- Compute each next term directly. To find the largest prime factor of the current term, trial-divide a temporary copy, removing all copies of each divisor.
- When divisor² exceeds the remaining copy, any remainder above 1 is prime and is the largest factor. Otherwise the last divisor removed was the largest. Use 64-bit arithmetic for safe multiplication in the loop condition.
- The terms through position ten are 2,4,6,9,12,15,20,25,30,35. For example, 12 has largest prime factor 3, giving 15; 15 has largest prime factor 5, giving 20. Only N−1 updates are needed.
Why it works
Trial division removes factors in increasing order. Once the remaining value has no divisor at most its square root, it is prime, so the helper returns exactly the largest prime divisor. Starting at term 1 and applying the recurrence N−1 times therefore returns term N.
Complexity: O(N√A) time as a conservative bound, where A is the largest generated term, and O(1) space. Removing factors reduces the practical trial range substantially.
Watch out. Do not use the largest proper divisor; it must be prime. Remove repeated factors completely. N = 1 returns 2.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
using namespace std;
long long largestPrimeFactor(long long value) {
long long largest = 1;
for (long long divisor = 2; divisor <= value / divisor; divisor++) {
while (value % divisor == 0) {
largest = divisor;
value /= divisor;
}
}
// Once trial division stops, any leftover factor is prime.
if (value > 1) {
largest = value;
}
return largest;
}
int main() {
int n;
cin >> n;
long long term = 2;
for (int index = 1; index < n; index++) {
term += largestPrimeFactor(term);
}
cout << term << '\n';
}