How to Solve HCF and LCM Problems
Solve HCF and LCM aptitude problems using prime factorization and the Euclidean method, with a worked example and practice questions with answers.
Expected Interview Answer
HCF (highest common factor) is the largest number dividing all given numbers, LCM (least common multiple) is the smallest number divisible by all of them, and for two numbers HCF × LCM = product of the numbers.
Find HCF via prime factorization (product of common primes to the lowest power) or the Euclidean algorithm (repeated division). Find LCM via prime factorization (product of all primes to the highest power) or LCM = (a × b) ÷ HCF for two numbers. HCF problems usually involve the largest quantity that divides several given quantities evenly (tiling, grouping); LCM problems involve events repeating together (bells ringing, traffic lights). Always reduce fractions using HCF and combine fraction denominators using LCM.
- One relation (HCF × LCM = product) links both quantities
- The Euclidean algorithm finds HCF quickly for large numbers
- Recognizing the "divides evenly" vs "repeats together" pattern picks the right tool instantly
AI Mentor Explanation
Two bowlers complete their overs in sets of 18 and 24 balls respectively. To find the biggest group size that divides both spells evenly, you want the HCF of 18 and 24, which is 6. If instead you ask when both bowlers next start a fresh spell together, counting from over one, you want the LCM, which is 72. HCF finds the largest shared divisor; LCM finds the smallest shared multiple — the same two numbers, two different questions.
Worked example (prime factorization)
18
- = 2¹ × 3²
24
- = 2³ × 3¹
HCF / LCM
- HCF = 2¹×3¹ = 6
- LCM = 2³×3² = 72
Step-by-Step Explanation
Step 1
Prime factorize each number
Break every number into its prime factors with exponents.
Step 2
HCF: lowest shared powers
Multiply each common prime at its lowest exponent across all numbers.
Step 3
LCM: highest powers
Multiply every prime present at its highest exponent across all numbers.
Step 4
Cross-check for two numbers
HCF × LCM = product of the two numbers — use this to verify.
What Interviewer Expects
- Clear distinction between "divides evenly" (HCF) and "repeats together" (LCM) problem framing
- Correct prime factorization method
- Knowledge of HCF × LCM = product (for two numbers)
- Awareness of the Euclidean algorithm as a faster alternative for large numbers
Common Mistakes
- Confusing which quantity (HCF or LCM) the word problem is actually asking for
- Using highest powers for HCF or lowest powers for LCM (swapped)
- Applying HCF × LCM = product to three or more numbers (only valid for two)
- Forgetting to reduce fractions with HCF before adding with LCM denominators
Best Answer (HR Friendly)
“HCF is the biggest number that divides everything evenly; LCM is the smallest number everything divides into. I prime-factorize each number, take the lowest shared powers for HCF and the highest powers for LCM. For two numbers, HCF times LCM always equals their product, which is a handy check.”
Follow-up Questions
- How does the Euclidean algorithm compute HCF for large numbers?
- Does HCF × LCM = product hold for three or more numbers?
- How do you find the HCF or LCM of fractions?
- How would you find the largest tile size that evenly fits a 24m by 18m room?
MCQ Practice
1. HCF of 18 and 24 is?
18 = 2×3², 24 = 2³×3; common primes at lowest power: 2¹×3¹ = 6.
2. LCM of 18 and 24 is?
Highest powers of all primes: 2³×3² = 72. Check: 6 × 72 = 432 = 18 × 24.
3. Two bells ring every 18 and 24 minutes and ring together at 9:00. They next ring together at?
They coincide every LCM(18,24) = 72 minutes = 1h12m after 9:00, i.e., 10:12.
Flash Cards
HCF method? — Prime factorize; multiply common primes at their lowest shared power.
LCM method? — Prime factorize; multiply all primes at their highest power.
HCF × LCM for two numbers? — Equals the product of the two numbers — a useful check.
"Repeats together" problems use? — LCM (e.g., bells, buses, blinking lights syncing again).