cppAcademy
FROM LEARNING TO COMPETING

Real problems.
Your next challenge.

Explore the Group C Olympiad archive.
Choose a topic. Find a challenge. Build your solution.

213 tasks across the Municipal, Regional, and National rounds (2009–2026), plus 4 previously featured problems. 146 tasks have independently written English summaries, analyses, and C++17 solutions; the remaining entries link to Arena. Topic tags are from Arena or our reviewed explanations. Difficulty labels are learning estimates, not official ratings.
GROUP C2009 · MediumPrime Factorization

Prime Factors of a Factorial

National Olympiad — Municipal round

Submission name: fact.cpp

Solve in Editor →

Problem summary

For N!, sum the exponents in its prime factorization.

Input

One integer N.

Output

The exponent sum.

Constraints

1 < N < 9999.

Worked example

An independently prepared example for this explanation.

Input

5

Output

5

Solution analysis

  1. For each prime p, count multiples of p, p², and so on in 1…N.
  2. Add these counts over all primes, using a sieve to identify them.

Why it works

Every factor p contributes once per power of p dividing its source integer. The multiple counts therefore count every prime factor with its multiplicity.

Complexity: O(N log log N) time and O(N) space.

Watch out. Count multiplicities, not just distinct primes.

Commented C++17 solution

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<bool>prime(n+1,true);
    long long ans=0;
    for(int p=2;p<=n;p++){
        if(prime[p]){
            // Legendre's formula: divide repeatedly to avoid power overflow.
            for(int x=n/p;x;x/=p){
                ans+=x;
            }
            for(int j=p+p;j<=n;j+=p){
                prime[j]=false;
            }
        }
    }
    cout<<ans<<'\n';
}

Source: Arena Olimpiici ↗