1 of 12

COMPUTATIONAL THINKING

By

​

​

Dept. of CSE

PVPSIT, Kanuru.

​

​

PRASAD V. POTLURI SIDDHARTHA INSTITUTE OF TECHNOLOGY

2 of 12

  • Problem:
  • Given two positive non-zero integers n and m design an algorithm for finding their greatest common divisor (usually abbreviated as gcd).
  • Algorithm development
  • Approach 1 (Not an Efficient Approach)
  • It is somewhat different from other problems we have probably encountered.
  • The difficult aspect of the problem involves the relationship between the divisors of two numbers.
  • Our first step might therefore be to break the problem down and find all divisors of the two integers n and m.
  • We may expect that this algorithm will be relatively time consuming for large values of n and m.

Dept of CSE

2025 - 26

THE GREATEST COMMON DIVISOR OF TWO INTEGERS

PVPSIT (Autonomous)

Problem Solving Techniques

3 of 12

  • Approach 2 (Efficient Approach) Euclid’s Algorithm
  • Greek philosopher, Euclid, more than 2000 years ago proposed this.
  • The gcd of two integers is the largest integer that will divide exactly into the two numbers with no remainder.
  • Example: number 30
  • The divisor 5 divides the number 30 up into 6 equal parts.

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

4 of 12

  • Example: n=30 and m=18

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

5 of 12

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

6 of 12

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

7 of 12

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

8 of 12

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

9 of 12

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

10 of 12

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

11 of 12

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

12 of 12

  • Applications
  • Reducing a fraction to its lowest terms.

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques