lab1-kgashok.py
Table of Contents
Lab 1: Compute the gcd of two numbers
[TOC]
Problem statement
Write a Python program to compute the greatest common divisor (gcd) of two positive integers.
Solution Key
CloudCoder Exercise
http://cloudcoder.kgkite.ac.in/cloudcoder/#exercise?c=80,p=6941
Related material
How to find the gcd of two numbers using prime factorization? http://j.mp/gcdPrime
Why 1 is the common factor? http://j.mp/gcdOne
Pre-Lab Questions
Show your manual workings for the gcd of 924 and 2562.
What is the practical use of calculating the
gcd
of two numbers?If you have written the recursive solution of the Euclid algorithm, then write the iterative solution, and vice versa.
How does the algorithm for the
gcd
of two numbers work? What is the name for this algorithm? Why is it so special?Why is the
global
keyword used in the functionget_twonumbers
?Is the function
get_twonumbers()
fruitful or not fruitful?Define a function
is_valid_year
with parameteryear
. The function must returnTrue
if the value ofyear
is between 1900 and 3000 (inclusive). Otherwise, it must returnFalse
.
Post-lab Questions
What if
a
or/andb
are negative integers? How will you modify the program to handle this? Clue: Use theabs()
function.
Bonus 1
How will find the
gcd
of three integers?How do you calculate the number of days in a month?
Related Material
PPT Slides showing the Recursive Calls
http://j.mp/gcdDemo
Recursion vs Iteration
Related Problems
Days per month
Last updated