Counting Distinct Prime Factors in Factorials

Given a positive integer m, you are required to compute the number of distinct prime factors in m! (the factorial of m). Recall that m! is defined as

\(m! = 1 \times 2 \times 3 \times \cdots \times m\)

Since m! is a product of all integers from 1 to m, its prime factors are precisely the prime numbers less than or equal to m.
Your task is to count the number of primes p such that \(p \le m\).

Examples:

• If m = 1, then 1! = 1 and it has no prime factors, so the answer is 0.
• If m = 2, then 2! = 2 which has one prime factor (2), so the answer is 1.
• If m = 5, then 5! = 120 and the primes up to 5 are 2, 3, and 5, thus the answer is 3.

inputFormat

The input consists of a single integer m provided via standard input (stdin).

\(1 \le m \le 10^5\)

outputFormat

The output should be a single integer printed on standard output (stdout), representing the number of distinct prime numbers that divide m!.

1

0