AtCoder Beginner Contest - Div Game

Official Analysis

Time Complexity: $\mathcal{O}(\sqrt{N})$

We can prime factorize $N$ as $N = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}$. To achieve the maximum number of operations, for each prime $p_i$, we should first choose $z = p_i^1$, then $z = p_i^2$ and so on.

As we prime factorize and find the exponent of each prime, we can decrement the exponent by $1$, then $2$, and so on, as long as the exponent stays nonnegative. Each time we decrement the exponent, we can add $1$ to the answer.

#include <iostream>
using namespace std;
 
int main()
{
	long long n;
	cin >> n;
	int ans = 0;
	//prime factorize n
	for (long long p = 2; p * p <= n; p++)