# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* prathamshalya

*tabr*

**Tester:***iceknight1093*

**Editorialist:**# DIFFICULTY:

TBD

# PREREQUISITES:

Sieve of Eratosthenes, prefix sums

# PROBLEM:

Let f(N) denote the largest factor of N that is not N itself. f(1) = 0.

You’re given K. Find the sum of all N such that f(N) = K.

# EXPLANATION:

First, observe that f(N) = \frac{N}{p}, where p is the smallest *prime* factor of N.

So, if we want f(N) = K, we must have N = K\cdot p, where p should be the smallest prime factor of N.

Clearly, choosing different values of p will give us different values of p, so we can instead focus on which p can possibly be chosen.

Since N = K\cdot p, every prime factor of N will also be a prime factor of K; except possibly p itself.

In particular, let q denote the smallest prime factor of K.

Then,

- If p \gt q, p will definitely not be the smallest prime factor of N since q will also divide it.
- If p \leq q, p will definitely be the smallest prime factor of N.

So, the only valid integers N are those of the form K\cdot p, where p is a prime that doesn’t exceed q.

We’re now left with two tasks: finding q quickly, and then computing the answer.

One way to find q is to simply precompute it for every integer between 1 and 10^6 before answering the test cases.

Let \text{spf}[n] denote the smallest prime factor of n. Initially, set this to 0 for every n.

Then, do the following:

- Iterate over integers p from 2 to 10^6.
- If \text{spf}[p] = 0 then p is a prime, otherwise it isn’t.

- If p is a prime, iterate over all its multiples.

For each multiple x, if \text{spf}[x] = 0, set \text{spf}[x] = p.

At the end of this process, the \text{spf} array will hold the values we want.

The complexity of this is \mathcal{O}(M\log\log M), where M = 10^6.

This is because the complexity of the algorithm is

and the sum of the reciprocals of the primes exhibits log-log growth.

Once q is known, we want to compute the sum of K\cdot p across all primes p \leq q.

Note that this is just K multiplied by the sum of all primes that don’t exceed q.

Our earlier sieve also told us which integers are primes, and so the sum of all primes not exceeding q can be computed from there using a simple prefix sum.

# TIME COMPLEXITY:

\mathcal{O}(1) per testcase after \mathcal{O}(M\log \log M) precomputation, where M = 10^6.

# CODE:

## Author's code (C++)

```
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
const int N = 1e6 + 69;
int sp[N];
int p[N];
void Solve()
{
int n; cin >> n;
int x = sp[n];
int ans = p[x];
ans *= n;
assert(n != 1);
cout << ans << "\n";
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
for (int i = 2; i < N; i++){
if (sp[i] == 0){
p[i] = i;
}
p[i] += p[i - 1];
for (int j = i; j < N; j += i){
if (sp[j] == 0) sp[j] = i;
}
}
cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
```

## Editorialist's code (Python)

```
maxn = 10**6
spf = [0]*maxn
pref = [0]*maxn
for i in range(2, maxn):
pref[i] = pref[i-1]
if spf[i] == 0:
pref[i] += i
for j in range(i, maxn, i):
if spf[j] == 0: spf[j] = i
for _ in range(int(input())):
k = int(input())
p = spf[k]
print(k * pref[p])
```