Founding Batch Offer ยท HLD ยท LLD ยท System Design at โ‚น799 until 30 Nov

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.

IntermediatePhase 2 - Level 3: Mathematical & Logical PatternsExample 4 of 13
find-hcf-gcd-using-loops.py
1# Take two numbers
2a = int(input("Enter first number: "))
3b = int(input("Enter second number: "))
4
5# Find GCD
6gcd = 1
7smaller = min(a, b)
8
9for i in range(1, smaller + 1):
10 if a % i == 0 and b % i == 0:
11 gcd = i
12
13print(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. 1

    Initialize gcd to one and find the smaller input.

  2. 2

    Try each positive candidate through that smaller value.

  3. 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.