Highest Power of a Prime Number Dividing a Factorial
Quantitative Aptitude › Number System · Topic 1.19
The highest power of a prime p that divides n! is the sum of the whole parts of n/p, n/p2, n/p3 and so on, a result called Legendre's formula. For a composite divisor, factorize it into primes and take the smallest ratio.
5 min read · Quantitative Aptitude · Number System
Quick Answer
The highest power of a prime p that divides n! is the sum of the whole parts of n/p, n/p2, n/p3 and so on, a result called Legendre’s formula. For a composite divisor, factorize it into primes and take the smallest ratio.
At a Glance
- Formula floor(n/p) + floor(n/p2) + …
- Power of 2 in 50! 47
- Power of 3 in 100! 48
- Power of 7 in 100! 16
- Composite divisor Minimum over primes of (power ÷ exponent)
- Special case p = 5 gives trailing zeros
Where Does It Fit?
This topic follows Problems on Consecutive Integers and Their Properties and generalises Factorial Values and Number of Trailing Zeros in a Factorial and Number of Trailing/Leading Zeros in the Product of Consecutive Numbers, where the prime was 5. It applies the prime factorization of Number of Factors, Sum of Factors and Product of Factors of a Number.
What Is Legendre’s Formula?
In short: count how many multiples of p, p2, p3 … lie up to n; each multiple of p adds one p, each multiple of p2 adds one more, and so on.
Legendre’s formula
- The highest power of a prime p dividing n! = floor(n/p) + floor(n/p2) + floor(n/p3) + … until the quotient is 0.
| n! and p | Working | Highest power |
|---|---|---|
| 100! and 3 | 33 + 11 + 3 + 1 | 48 |
| 50! and 2 | 25 + 12 + 6 + 3 + 1 | 47 |
| 100! and 7 | 14 + 2 | 16 |
| 100! and 5 | 20 + 4 | 24 |
| 100! and 11 | 9 | 9 |
| 30! and 3 | 10 + 3 + 1 | 14 |
The extra terms for p2, p3 count numbers such as 9, 18, 27 that contain more than one factor of 3. The method is the same as the zero count in Factorial Values and Number of Trailing Zeros in a Factorial, where p = 5.
How Do You Handle a Composite Divisor?
In short: factorize the divisor into primes, find the power of each prime in n!, divide by that prime’s exponent in the divisor, and take the smallest result.
- For the highest power of 12 = 22 × 3 in 30!: the power of 2 is 15 + 7 + 3 + 1 = 26, giving 26 ÷ 2 = 13; the power of 3 is 10 + 3 + 1 = 14. The smaller value is 13.
- For 6 = 2 × 3 in 50!: the power of 2 is 47 and of 3 is 22, so the answer is 22.
- For 18 = 2 × 32 in 40!: the power of 2 is 38 and of 3 is 18, giving 38 and 18 ÷ 2 = 9. The smaller is 9.
- For 10 in 100!: the power of 2 is 97 and of 5 is 24, so there are 24 zeros.
How Do You Use the Formula in Different Question Types?
In short: identify the prime, apply the formula, and watch for the limiting prime.
- Find the largest n such that 2n divides 20!: 10 + 5 + 2 + 1 = 18.
- Find the largest n for 20n = 22 × 5 in 50!: 2s give 47 ÷ 2 = 23 and 5s give 12, so n = 12.
- Count the powers of a large prime: for 13 in 100!, the quotient is 7 and the next term is 0, so the answer is 7.
Factorials are developed again in the counting chapter at Fundamental Principle of Counting (Addition and Multiplication Rules).
Solved Examples
Example 1
Question: Find the highest power of 3 that divides 100!.
- floor(100/3) = 33.
- floor(100/9) = 11, floor(100/27) = 3, floor(100/81) = 1.
- Total = 33 + 11 + 3 + 1.
Answer: 48.
Example 2
Question: Find the highest power of 2 that divides 50!.
- floor(50/2) = 25, floor(50/4) = 12, floor(50/8) = 6.
- floor(50/16) = 3, floor(50/32) = 1.
- Total = 25 + 12 + 6 + 3 + 1.
Answer: 47.
Example 3
Question: Find the largest n such that 12n divides 30!.
- 12 = 22 × 3. Power of 2 in 30! = 15 + 7 + 3 + 1 = 26.
- Power of 3 in 30! = 10 + 3 + 1 = 14.
- n = min(26 ÷ 2, 14) = min(13, 14).
Answer: 13.
Example 4
Question: Find the largest n such that 18n divides 40!.
- 18 = 2 × 32. Power of 2 in 40! = 20 + 10 + 5 + 2 + 1 = 38.
- Power of 3 in 40! = 13 + 4 + 1 = 18, so 18 ÷ 2 = 9.
- n = min(38, 9).
Answer: 9.
Example 5
Question: Find the highest power of 7 that divides 100!.
- floor(100/7) = 14.
- floor(100/49) = 2.
- Total = 14 + 2.
Answer: 16.
Shortcuts and Tricks
- Keep dividing by p and add the quotients; drop remainders.
- For a composite divisor, divide each prime’s power by its exponent in the divisor.
- The limiting prime is usually the largest prime in the divisor.
- For 2 in n!, the answer is n minus the number of 1s in the binary form of n.
- For primes larger than n/2, the answer is 1.
Common Mistakes
- Forgetting to divide by the exponent of the prime in a composite divisor.
- Stopping after the first division.
- Taking the largest ratio instead of the smallest.
- Using non-prime p in the formula.
- Rounding up instead of taking the whole part.
Practice Questions
- Find the highest power of 5 that divides 100!.
- Find the highest power of 11 that divides 100!.
- Find the highest power of 13 that divides 100!.
- Find the largest n such that 6n divides 50!.
- Find the highest power of 3 that divides 60!.
- Find the highest power of 2 that divides 20!.
Answers: 1) 24; 2) 9; 3) 7; 4) 22; 5) 28; 6) 18.
Why Is This Topic Important?
- General method Works for every prime and every composite divisor.
- Exam use Frequent in number system sets.
- Link Generalises Factorial Values and Number of Trailing Zeros in a Factorial.
- Link Uses Number of Factors, Sum of Factors and Product of Factors of a Number.
What Comes Next?
The next topic is Expressing a Number as a Sum/Difference of Two Squares, which expresses numbers as sums or differences of two squares.
Key Terms and Formulas
- Legendre’s formula Sum of floor(n/pk)
- Floor Whole part of a quotient
- Prime power p raised to a positive exponent
- Composite divisor A divisor made of several primes
- Limiting prime The prime giving the smallest ratio
- Factorial Product of 1 to n
Related Topics
- Problems on Consecutive Integers and Their Properties
- Expressing a Number as a Sum/Difference of Two Squares
- Classification of Numbers (Natural, Whole, Integers, Rational, Irrational and Real Numbers)
- Face Value and Place Value of Digits
Exam Corner
Points to Remember
- Power of p in n! = floor(n/p) + floor(n/p2) + …
- Composite divisor: take the minimum over primes.
- Power of 2 in 50! is 47; of 3 in 100! is 48.
- p = 5 gives trailing zeros.
- Divide each prime’s power by its exponent in the divisor.
Do Not Confuse With
- Power of a prime vs of a composite A composite needs the minimum over primes.
- Floor vs rounding Always drop the remainder.
- Power of 2 vs of 5 Different primes give different counts.
- n! vs n The formula is about the factorial.
Memory Hook
Divide by p, by p squared, by p cubed, and add the whole parts.
GS Relevance
Frequently Asked Questions
What is Legendre's formula?
Legendre's formula gives the highest power of a prime p dividing n factorial as the sum of the whole parts of n divided by p, p squared, p cubed and so on, until the quotient is zero. The highest power of 3 in 100 factorial is 33 plus 11 plus 3 plus 1, which is 48.
How do you find the highest power of a composite number in a factorial?
To find the highest power of a composite number in a factorial, factorize the composite into primes, find the highest power of each prime in the factorial, divide each by the prime's exponent in the composite, and take the smallest result. For 12 in 30 factorial, the answer is the smaller of 13 and 14, which is 13.
What is the highest power of 2 in 50 factorial?
The highest power of 2 that divides 50 factorial is 47. It is found by adding the whole parts of 50 divided by 2, 4, 8, 16 and 32, which are 25, 12, 6, 3 and 1. The next quotient, for 64, is zero, so the sum is 47.
How is this related to trailing zeros?
The trailing zeros of a factorial are the special case where the prime is 5, because each zero needs a factor 2 and a factor 5 and the 5s are fewer. For 100 factorial, the highest power of 5 is 20 plus 4, which is 24, so there are 24 trailing zeros.
What is the highest power of a prime larger than n over 2 in n factorial?
For a prime larger than n over 2 and at most n, the highest power in n factorial is exactly 1, because only the prime itself is a multiple of it up to n. For example, the prime 53 divides 100 factorial exactly once, since 106 is greater than 100.
PYQ Practice — Statement Analysis
1 The highest power of 3 dividing 100! is 48.
33 + 11 + 3 + 1 = 48.
2 The highest power of 7 dividing 100! is 14.
It is 14 + 2 = 16, because 49 also contributes.
3 The largest n such that 12n divides 30! is 13.
min(26 ÷ 2, 14) = 13.
4 The number of trailing zeros of 100! equals the highest power of 5 dividing it.
That power is 24, which equals the zeros.
Related Topics
Browse the full Quantitative Aptitude index