AtCoder Beginner Contest - Div Game

Official Analysis

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.

Implementation

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

Copy
#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++) {

Copy
import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Kattio io = new Kattio();
		long n = io.nextLong();

		int ans = 0;
		// prime factorize n

Copy
n = int(input())

ans = 0
# prime factorization for n
for p in range(2, int(n**0.5)):
	e = 0
	while n % p == 0:
		n /= p
		e += 1
	# here p^e divides n