Find HCF (GCD) Using Loops
Find a greatest common divisor by scanning possible factors. Students update the best common divisor and see this basic loop's positive-input assumption.
1# Take two numbers2a = int(input("Enter first number: "))3b = int(input("Enter second number: "))45# Find GCD6gcd = 17smaller = min(a, b)89for i in range(1, smaller + 1):10 if a % i == 0 and b % i == 0:11 gcd = i1213print(f"GCD of {a} and {b} is {gcd}")
Output
Enter first number: 48 Enter second number: 18 GCD of 48 and 18 is 6
In this one
- Track the best common divisor
- Use increasing candidates
- Assume positive operands
How it works
- 1
Initialize gcd to one and find the smaller input.
- 2
Try each positive candidate through that smaller value.
- 3
Replace gcd whenever both remainders are zero.
Edge cases
Does the scan support zero reliably?
Does the scan support zero reliably?
No. It assumes two positive integers.
Why keep replacing gcd?
Why keep replacing gcd?
Later matching candidates are larger.
What's going on
A common divisor divides both inputs exactly. Candidates rise from one through the smaller number, and each successful candidate replaces gcd.
Because candidates increase, the final stored match is the greatest one. For 12 and 18 it becomes six. This simple scan assumes positive inputs; zero or negatives can leave the initial one unchanged even when that is not the correct GCD.
Does the scan support zero reliably? No. It assumes two positive integers.
Why keep replacing gcd? Later matching candidates are larger.
Quiz
Tap an option. The answer stays hidden until you pick.
Question 1
Which operator joins the factor tests?
Pick an answer to check it.
Question 2
Does the scan support zero reliably?
Pick an answer to check it.
Questions people ask
Does the scan support zero reliably?
No. It assumes two positive integers.
Why keep replacing gcd?
Later matching candidates are larger.
Which operator joins the factor tests?
and.
๐Related Content
- ๐
Phase 2 - Learn Concepts
Review Phase 2 concepts and explanations
- ๐
Phase 2 - Quiz
Test your Phase 2 understanding with quiz questions
- ๐ป
Phase 2 - All Practice Problems
Explore all practice problems for Phase 2
- ๐
Master Your Logic Building - Complete Course
Browse all phases and tutorials
- ๐ง
Logic Building Overview
Learn about the complete logic building curriculum