Skip to content
Technique

How many times a prime divides : count multiples, then multiples of its square

Quantitative Aptitude • Number System

Statement

Each multiple of up to holds at least one factor . A multiple of (such as when ) holds a second one, a multiple of a third. So the total count is: (number of multiples of ) (number of multiples of ) , stopping when the power is bigger than . The number of multiples of up to is the whole-number part of .

How to use it

  1. 1Count the multiples of up to .
  2. 2Count the multiples of , then , while they are at most .
  3. 3Add the counts.

Worked example

How many times does 2 divide ?

Step-by-step

  1. 1
    Multiples of 2 up to 10: 2, 4, 6, 8, 10, which is 5.

    Why: Each gives one 2.

  2. 2
    Multiples of 4: 4, 8, which is 2.

    Why: Each holds a second 2.

  3. 3
    Multiples of 8: 8, which is 1.

    Why: 8 holds a third 2.

  4. 4
    .

Answer

8

Watch out

Counting only the multiples of misses the extra factors in multiples of ; this gives an answer too small by exactly that many.

Builds on

Also known as

power of a prime in a factorial, Legendre's formula, highest power dividing n factorial

Appears in past papers

2022

2020