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
- 1Count the multiples of up to .
- 2Count the multiples of , then , while they are at most .
- 3Add the counts.
Worked example
How many times does 2 divide ?
Step-by-step
- 1Multiples of 2 up to 10: 2, 4, 6, 8, 10, which is 5.
Why: Each gives one 2.
- 2Multiples of 4: 4, 8, which is 2.
Why: Each holds a second 2.
- 3Multiples of 8: 8, which is 1.
Why: 8 holds a third 2.
- 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