GRE Quant lesson · Primes
GRE primes and prime factorization: divisors, zeros and powers
Prime factorization for GRE Quant: spotting primes, distinct prime factors, the divisor formula, trailing zeros, powers of p in a factorial, perfect squares.
The core idea
Every integer greater than 1 is a unique product of primes, and most number-property questions get easy once you write that product. Read divisor counts, trailing zeros, perfect squares and powers of a prime straight off the exponents.
Core ideas
Words used here
- Factor (or divisor): a whole number that divides another with nothing left over.
- Prime: a whole number above 1 whose only positive divisors are 1 and itself: 2, 3, 5, 7, 11, 13, …
- Composite: a whole number above 1 that is not prime, such as 9 = 3 × 3.
- Exponent: the small raised number. 2³ means 2 × 2 × 2 = 8.
- Prime factorization: a number written as a product of primes, such as 360 = 2³ × 3² × 5.
- Distinct: different. 12 = 2 × 2 × 3 has two distinct primes, 2 and 3.
- Perfect square: a whole number times itself (36 = 6 × 6). Perfect cube: a whole number used three times (8 = 2 × 2 × 2).
- Factorial: n! = n × (n − 1) × … × 2 × 1. For example, 5! = 120.
- √n (square root of n): the number that, times itself, gives n. √49 = 7.
- A prime has exactly two positive divisors: 1 and itself. 1 is not prime (it has only one divisor). 2 is the only even prime.
- Every integer above 1 is a product of primes in exactly one way. Divide by the smallest prime that works, again and again: 360 ÷ 2 = 180, 180 ÷ 2 = 90, 90 ÷ 2 = 45, 45 ÷ 3 = 15, 15 ÷ 3 = 5, 5 ÷ 5 = 1. So 360 = 2 × 2 × 2 × 3 × 3 × 5 = 2³ × 3² × 5.
- Number of positive divisors of pᵃ × qᵇ × rᶜ is (a + 1)(b + 1)(c + 1).
- Perfect squares have only even exponents (36 = 2² × 3²). Perfect cubes have exponents that are multiples of 3 (216 = 2³ × 3³).
- Power of p in n!: n ÷ p + n ÷ p² + n ÷ p³ + …, keeping only the whole-number part of each division.
Try it. Write 252 as a product of primes. Then count its positive divisors.
Show the answer
- 252 ÷ 2 = 126, 126 ÷ 2 = 63, 63 ÷ 3 = 21, 21 ÷ 3 = 7, 7 ÷ 7 = 1.
- So 252 = 2² × 3² × 7.
- Divisors: (2 + 1) × (2 + 1) × (1 + 1) = 3 × 3 × 2 = 18.
Spotting primes
To test whether n is prime, check whether any prime up to √n (the square root of n) divides it. If none does, n is prime. Why only up to √n? If n = a × b, one of a and b is at most √n, so a factor would already have appeared.
Quick tests: an even number above 2 is not prime. A number ending in 0 or 5 is a multiple of 5. A number is a multiple of 3 when its digits add up to a multiple of 3.
How to spot it: "how many primes are there between …?", "which of the following is prime?"
Example. How many primes are there between 30 and 50?
- Remove the even numbers and the numbers ending in 5. Left: 31, 33, 37, 39, 41, 43, 47, 49.
- 7 × 7 = 49, so √50 is just above 7. Test the primes 3 and 7 (2 and 5 are already ruled out).
- 33 = 3 × 11, 39 = 3 × 13 and 49 = 7 × 7, so they are not prime.
- Primes: 31, 37, 41, 43 and 47, which is 5.
Trap: counting 49 or 39 because they "look" prime.
Edge cases.
- 1 is not prime (it has only one factor). 2 is the only even prime. Negative numbers aren't prime.
- Big numbers can hide two medium primes: 221 = 13 × 17. Test every prime up to √221 ≈ 14.9.
- An odd sum of two primes must use 2, because two odd primes add to an even number.
GRE-level example. p and q are primes, and p + q = 31. What is pq?
- 31 is odd. Two odd numbers add to an even number, so one of the primes must be the only even prime, 2.
- The other is 31 − 2 = 29, which is prime (no prime up to √29 ≈ 5.4 divides it).
- pq = 2 × 29 = 58.
On the GRE (select all). "Which of the following integers are prime? 1, 2, 51, 59, 91, 97." 1 is not prime, 2 is, 51 = 3 × 17 and 91 = 7 × 13 are not, and 59 and 97 have no prime factor up to their square roots (below 8 and 10). Select 2, 59 and 97.
Check yourself. Is 221 prime?
Check your answer
No: 221 = 13 × 17.
Distinct prime factors
Factor the number into primes completely. Then list each prime once (distinct means different), however large its exponent is.
Why it works. Every integer above 1 has exactly one prime factorization (apart from the order of the factors). So its list of distinct primes is fixed, however you start splitting it.
How to spot it: "how many different prime factors?", "the sum of the distinct prime factors".
Example. How many distinct prime factors does 1,260 have?
- 1,260 ÷ 2 = 630, 630 ÷ 2 = 315, 315 ÷ 3 = 105, 105 ÷ 3 = 35, 35 ÷ 5 = 7, 7 ÷ 7 = 1.
- So 1,260 = 2² × 3² × 5 × 7.
- Distinct primes: 2, 3, 5 and 7, which is 4.
Trap: counting the 2² and the 3² twice each and answering 6.
Edge cases.
- Powers add no new primes: 2¹⁰ has one distinct prime factor.
- The distinct primes of a product are all the primes of either factor, each listed once.
- 1 has no prime factors.
GRE-level example. How many distinct prime factors does 30⁴ − 30² have?
- Factor out 30²: 30⁴ − 30² = 30²(30² − 1).
- 30² − 1 is a difference of squares: (30 − 1)(30 + 1) = 29 × 31.
- 30² = 2² × 3² × 5², so the number is 2² × 3² × 5² × 29 × 31.
- Distinct primes: 2, 3, 5, 29 and 31, which is 5.
On the GRE (Quantitative Comparison). Quantity A: the number of distinct prime factors of 30⁴. Quantity B: the number of distinct prime factors of 2 × 3 × 5 × 7. 30⁴ = 2⁴ × 3⁴ × 5⁴ has 3 distinct primes and 2 × 3 × 5 × 7 has 4, so Quantity B is greater. Counting the exponent 4 as "more primes" is the trap.
Check yourself. What is the sum of the distinct prime factors of 1,260?
Check your answer
2 + 3 + 5 + 7 = 17.
Number of divisors
Write the prime factorization, add 1 to each exponent, and multiply.
Why it works: take 360 = 2³ × 3² × 5¹. Every divisor of 360 is 2ᵃ × 3ᵇ × 5ᶜ, where a is 0, 1, 2 or 3 (4 choices), b is 0, 1 or 2 (3 choices) and c is 0 or 1 (2 choices). The + 1 is the choice "exponent 0". Choices for different primes multiply.
How to spot it: "how many positive divisors (factors) does n have?" for a large n.
Example. How many positive divisors does 360 have?
- 360 = 2³ × 3² × 5¹.
- (3 + 1) × (2 + 1) × (1 + 1) = 4 × 3 × 2 = 24.
Only perfect-square divisors. A square divisor needs even exponents. For 360: the 2 can have exponent 0 or 2 (2 choices), the 3 can have 0 or 2 (2 choices), and the 5 only 0 (1 choice). 2 × 2 × 1 = 4 square divisors: 1, 4, 9 and 36.
Trap: adding the exponents (3 + 2 + 1 = 6). That counts the prime factors, not the divisors.
Try it. How many positive divisors does 200 have?
Show the answer
- 200 = 2 × 100 = 2 × 2 × 2 × 5 × 5 = 2³ × 5².
- (3 + 1) × (2 + 1) = 4 × 3 = 12.
Edge cases.
- Odd divisors: drop the 2s. 360 has (2 + 1)(1 + 1) = 6 odd divisors, so 24 − 6 = 18 are even.
- An odd number of divisors happens exactly for perfect squares.
- Exactly 3 divisors means the square of a prime (4, 9, 25, …).
GRE-level example. The only prime factors of n are 2 and 3 (both appear), and n has exactly 15 positive divisors. What is the smallest possible n?
- n = 2ᵃ × 3ᵇ with a, b ≥ 1, so (a + 1)(b + 1) = 15.
- Both brackets are at least 2, so they are 3 and 5: (a, b) = (2, 4) or (4, 2).
- 2² × 3⁴ = 4 × 81 = 324 and 2⁴ × 3² = 16 × 9 = 144.
- Smallest: 144 (give the bigger exponent to the smaller prime).
Numeric Entry. "How many positive divisors does 360 have?" 360 = 2³ × 3² × 5, so (3 + 1)(2 + 1)(1 + 1) = 24. Type 24.
Check yourself. How many odd divisors does 360 have?
Check your answer
Ignore the 2s: 3² × 5 has (2 + 1)(1 + 1) = 6 divisors: 1, 3, 5, 9, 15, 45.
Trailing zeros of a factorial
Trailing zeros are the zeros at the end of a number (1,200 has two). Each one comes from a factor 10 = 2 × 5. In n! (n factorial) there are many more 2s than 5s, so count the 5s:
n ÷ 5 + n ÷ 25 + n ÷ 125 + …, keeping only the whole-number part each time.
Why divide by 25 too? A multiple of 25 = 5 × 5 holds two 5s, but n ÷ 5 counts only one of them. Each multiple of 125 holds a third 5, and so on.
How to spot it: "how many zeros does n! end with?"
Example. How many zeros does 130! end with?
- 130 ÷ 5 = 26.
- 130 ÷ 25 = 5.2, so keep 5.
- 130 ÷ 125 = 1.04, so keep 1.
- 130 ÷ 625 is less than 1, so stop.
- Total: 26 + 5 + 1 = 32.
Trap: stopping at 26. That misses the extra 5s inside 25, 50, 75, 100 and 125.
Try it. How many zeros does 60! end with?
Show the answer
- 60 ÷ 5 = 12.
- 60 ÷ 25 = 2.4, so keep 2.
- 60 ÷ 125 is less than 1, so stop. Total: 12 + 2 = 14.
Edge cases.
- Some counts are skipped. 24! ends in 4 zeros and 25! in 6 (25 brings two 5s), so no factorial ends in exactly 5 zeros.
- For a product that isn't a factorial, count the 2s and the 5s separately and take the smaller count.
- Zeros at the end only: the zeros inside a number (like the 0 in 105) don't count.
GRE-level example. How many zeros does 20⁵ × 35³ × 12² end with?
- 20⁵ = (2² × 5)⁵ = 2¹⁰ × 5⁵.
- 35³ = 5³ × 7³.
- 12² = (2² × 3)² = 2⁴ × 3².
- Total: 2¹⁴ and 5⁸. Each 10 needs one 2 and one 5, so there are 8 tens: 8 zeros.
On the GRE (Quantitative Comparison). Quantity A: the number of zeros at the end of 25!. Quantity B: the greatest integer k such that 3ᵏ divides 12!. A: 25 ÷ 5 = 5, plus one more from 25 = 5², so 6. B: 12 ÷ 3 = 4, plus one more from 9 = 3², so 5. Quantity A is greater.
Check yourself. Does any factorial end in exactly 5 zeros?
Check your answer
No. 20! to 24! end in 4 zeros, and 25! jumps to 6, because 25 = 5 × 5 adds two 5s at once.
Greatest power of a prime in a product
Count the factors of the prime p in each part of the product. For a factorial, use the same chain of divisions as for trailing zeros, with p in place of 5.
Why it works. Each multiple of 3 gives one factor of 3. Each multiple of 9 gives a second one, which the first division missed. Each multiple of 27 gives a third. Every further division counts one more layer.
How to spot it: "the greatest integer k such that pᵏ divides …".
Example. What is the greatest k such that 3k divides 60!?
- 60 ÷ 3 = 20 (multiples of 3).
- 60 ÷ 9 = 6.67, so keep 6 (multiples of 9 give a second 3).
- 60 ÷ 27 = 2.22, so keep 2 (multiples of 27 give a third 3).
- 60 ÷ 81 is less than 1, so stop.
- k = 20 + 6 + 2 = 28.
For a single number, keep dividing by the prime instead. 96 → 48 → 24 → 12 → 6 → 3: that is 5 halvings, and 3 is odd. So 96 = 2⁵ × 3, and the greatest power of 2 that divides 96 is 2⁵.
Trap: answering 20, the number of multiples of 3. It misses the extra 3s in 9, 18, 27 and so on.
Edge cases.
- A composite base is limited by its scarcest prime. For 6ᵏ dividing 60!, there are 56 twos but only 28 threes, so k = 28.
- A prime power base needs groups: 4ᵏ = 2²ᵏ, so the 56 twos in 60! make 28 fours.
GRE-level example. What is the greatest k such that 12ᵏ divides 30!?
- 12 = 2² × 3, so each 12 needs two 2s and one 3.
- 2s in 30!: 15 + 7 + 3 + 1 = 26, which make 13 pairs.
- 3s in 30!: 10 + 3 + 1 = 14.
- k is limited by the smaller: k = 13.
Check yourself. What is the greatest k such that 2ᵏ divides 40!?
Check your answer
20 + 10 + 5 + 2 + 1 = 38.
Making a perfect square
Factor the number and look at the exponents. A perfect square needs every exponent even; a perfect cube needs every exponent to be a multiple of 3. Multiply by exactly what is missing.
Why it works. A perfect square is some number times itself, so each of its primes appears the same number of times in each half: every exponent is even. A cube splits into three equal parts, so every exponent is a multiple of 3.
How to spot it: "the smallest positive integer k such that nk is a perfect square".
Example. What is the smallest positive integer k for which 180k is a perfect square?
- 180 ÷ 2 = 90, 90 ÷ 2 = 45, 45 ÷ 3 = 15, 15 ÷ 3 = 5, 5 ÷ 5 = 1. So 180 = 2² × 3² × 5.
- The exponents are 2, 2 and 1. Only the 5 has an odd exponent, so it needs one more 5: k = 5.
- Check: 180 × 5 = 900 = 30 × 30. ✓
For a perfect cube, raise every exponent to 3: one more 2, one more 3 and two more 5s. k = 2 × 3 × 5² = 2 × 3 × 25 = 150, and 180 × 150 = 27,000 = 30³.
Trap: answering 20 or 45. 180 × 20 = 3,600 = 60² and 180 × 45 = 8,100 = 90² are squares too, but k is not the smallest.
Edge cases.
- The smallest k uses only the missing primes. Any extra square factor (like 4 or 9) still gives a square, but a bigger k.
- A square and a cube at once needs every exponent to be a multiple of 6.
- Dividing instead of multiplying: the largest square that divides n uses each exponent rounded down to an even number.
GRE-level example. What is the smallest positive integer k such that 2³ × 3⁴ × 5 × k is a perfect cube?
- Raise each exponent to the next multiple of 3. 2³ is fine. 3⁴ needs two more 3s (to 3⁶). 5¹ needs two more 5s (to 5³).
- k = 3² × 5² = 9 × 25 = 225.
- Check: 2³ × 3⁶ × 5³ = (2 × 3² × 5)³ = 90³ ✓.
Check yourself. What is the smallest positive integer k such that 72k is a perfect square?
Check your answer
72 = 2³ × 3². Only the 2 has an odd exponent, so k = 2 (144 = 12²).
Remainders of primes
Every prime greater than 3 is odd and not a multiple of 3, so it sits right next to a multiple of 6: it is 6q + 1 or 6q + 5 (that is, 6q − 1). So its remainder when divided by 6 is 1 or 5, and never anything else.
Why it works. Any integer is 6q, 6q + 1, 6q + 2, 6q + 3, 6q + 4 or 6q + 5. The forms 6q, 6q + 2 and 6q + 4 are even, and 6q + 3 is a multiple of 3. A prime greater than 3 is neither, so only 6q + 1 and 6q + 5 are left. Squares go further: p² − 1 = (p − 1)(p + 1) is a product of two consecutive even numbers, so one of them is a multiple of 4 and the product is a multiple of 8. One of p − 1, p, p + 1 is a multiple of 3, and it isn't p, so (p − 1)(p + 1) is also a multiple of 3. That makes p² − 1 a multiple of 24.
How to spot it: "p is a prime number greater than 3" (or "greater than 5"), and a quantity about a remainder.
GRE-level example. p is a prime number greater than 3.
- Quantity A: the remainder when p² is divided by 24
- Quantity B: 1
- p² − 1 is a multiple of 24 (see above), so p² leaves remainder 1.
- Check: 5² = 25 = 24 + 1, 7² = 49 = 48 + 1, 11² = 121 = 120 + 1.
- The two quantities are equal.
Now change Quantity A to "the remainder when p is divided by 6" and Quantity B to 3. The remainder is 1 (for p = 7) or 5 (for p = 5), so one value is below 3 and one is above: the relationship cannot be determined.
Trap: treating the remainder of a prime as unknown (any of 0 to 5) or as fixed. It is exactly one of two values, 1 or 5.
Edge cases.
- The condition matters. If p is just "a prime number", p = 2 gives p² = 4 and p = 3 gives p² = 9, so the remainder by 24 is no longer always 1.
- Remainder by 4. Every odd prime leaves 1 or 3 when divided by 4, so "the remainder when p is divided by 4" against 2 cannot be determined.
Check yourself. p is a prime number greater than 3. Compare Quantity A, the remainder when p² + 2 is divided by 3, with Quantity B, 0.
Check your answer
p is not a multiple of 3, so p² leaves remainder 1 when divided by 3 (5² = 25 = 24 + 1, 7² = 49 = 48 + 1). Then p² + 2 leaves remainder 1 + 2 = 3, which is 0. The two quantities are equal.
How hard questions disguise it
For harder questions (L4–L5)
At L4 and L5, factorizations hide inside exponent expressions (125 × 183 is 213 × 311) or feed counting questions ("how many divisors of 720 are odd?" counts the divisors of the odd part, 45). Others ask for the largest k with 12k dividing 30!. Count the 2s (26) and the 3s (14) in 30! separately. Each 12 = 2² × 3 uses two 2s and one 3, so the 2s run out first: k = 26 ÷ 2 = 13. Always factor into primes first.
Practice
Practice prime factorization patterns in timed sets on the primes practice page.
Common traps
Adding exponents or forgetting the + 1
A divisor picks an exponent from 0 up to the full power for each prime, which is (e + 1) choices. The choices for different primes multiply; don't add the exponents or count the primes.
Dropping 1 and n, or adding negatives
The divisor formula already includes 1 and n, and it counts positive divisors only. Don't subtract 2 or double the result.
Counting square divisors wrong
A perfect-square divisor uses only even exponents, from 0 up to the prime's exponent in n. Count those choices for each prime and multiply.
Missing or double-counting the higher powers
Every multiple of p gives one factor of p, every multiple of p² one more, every multiple of p³ one more again. Add n ÷ p, n ÷ p², n ÷ p³ and so on, whole parts only.
Counting multiples of 10 or factors of 2
Each trailing zero needs a 2 and a 5. There are always more 2s than 5s, so the 5s decide the count. Multiples of 10 are already among the multiples of 5.
Miscounting how many times 2 divides a number
Keep halving until the result is odd, and count the halvings. The answer is that count, not the odd number left over and not 2 raised to it.
Counting 1 as prime, skipping 2, or judging by the last digit
1 is not prime, 2 is the only even prime, and many odd numbers (9, 21, 27, 49) are not prime. Test divisibility by the primes up to the square root.
Stopping before the factorization is complete
After dividing out the small primes, whatever is left may be prime itself, or may still factor. Keep going until every factor is prime.
Counting repeated primes or reporting the wrong one
'Distinct prime factors' counts each prime once, however many times it divides n. Then check whether the question wants their number, their sum, or the largest one.
Making a square when a cube is needed
A perfect cube needs every exponent to be a multiple of 3. Raise each exponent to the next multiple of 3, and answer with the multiplier k, not the cube or its root.
Counting a composite base in n!
Split the base into primes. Count each prime in n! with ⌊n/p⌋ + ⌊n/p²⌋ + …, divide by its exponent in the base, and take the smallest result: the scarcest prime decides.
Counting 1, missing 2, or trusting an odd number that looks prime
1 is not prime and 2 is. 51 = 3 × 17, 57 = 3 × 19 and 91 = 7 × 13 are not prime; test every prime up to the square root before you select a number.
Counting a repeated prime more than once
30⁴ = 2⁴ × 3⁴ × 5⁴ still has only 3 distinct prime factors. Raising a number to a power adds no new primes.
Missing the extra 5s in a factorial
25! has 25 ÷ 5 = 5 multiples of 5, and 25 itself gives one more 5, so it ends in 6 zeros, not 5.
Assuming a prime can leave any remainder
A prime greater than 3 leaves remainder 1 or 5 when divided by 6 (never 0, 2, 3 or 4), and its square always leaves remainder 1 when divided by 24.