Description
Part A: Euclid’s Algorithm
Euclid’s Algorithm was invented by the Greek mathematician Euclid about 2,300 years ago. The algorithm
calculates the greatest common divisor/factor (GCD) of two integers. (Please refer to your lecture for more
details about how and why it works).
Your task will be to implement Euclid’s Algorithm in Python in order to calculate the GCD of any two
numbers.
(a) Write a Python function euclid that takes two numbers as input and outputs their GCD. You may
assume that inputs are valid (the inputs are two integers).
Your Python function euclid should take two arguments num1 and num2, which are type int. It should
return an int that is the GCD of the two numbers.
1 def euclid ( num1 , num2 ):
2 # WRITE YOUR CODE HERE
3 return # your GCD
For example, these lines print the values for GCD(355, 55) and GCD(182, 19833).
1 print ( euclid (355 ,55) ) # should print 5
2 print ( euclid (182 , 19833) ) # should print 1
Your algorithm should also print out (but not return) the intermediate steps. By intermediate steps, we
mean each equivalent calculation of the GCD of the two numbers. The Euclidean algorihtm reduces your
initial GCD of two numbers into subsequent equivalent GCDs, if implemented correctly. For instance,
for 270 and 192:
GCD(270,192) = GCD(192,78) = GCD(78,36) = GCD(36,6) = GCD(6,0) = 6.
Your goal is to print out
GCD(270,192) = GCD(192,78) = GCD(78,36) = GCD(36,6) = GCD(6,0) = 6
precisely as shown above (with = separating each printed statement), on a single line.
(b) Run your algorithm on the specified inputs in the main function to make sure your algorithm works.
You may modify the main function to try other numbers but make sure to change it back, and do not
turn in a modified main function.
Part B: Prime Number Generation
Prime number generation is a crucial to many subfields of math and computer science, notably cryptography
and security. Here, you will implement another ancient algorithm known as the Sieve of Eratosthenes to
generate prime numbers.
(a) Write a Python function prime gen that implements the Sieve of Eratosthenes. Your function will take
in an integer n > 1 and will output all prime numbers up to (and including) n.
Your function prime gen will take in a single int as its argument and output a list of prime numbers
(each also of type int). Make sure your output is a list, or your code will get zero points.
1 def prime_gen (n):
2 # WRITE YOUR CODE HERE
3 return # your list of prime numbers
For example, the following lines print the primes up to 5 and 10:
1 print ( prime_gen (5) )
2 print ( prime_gen (10) )
where the output is:
1 [2 , 3, 5]
2 [2 , 3, 5, 7]
Page 2
(b) Run your algorithm on the specified inputs in the main function to make sure your algorithm works.
You may modify the main function to try other numbers but make sure to change it back, and do not
turn in a modified main function.
Part C: Primality Testing
Another useful algorithm to have for prime numbers is a primality checker. Primality checking is, again,
important to fields such as cryptography and computer security. Here, you will implement three different
primality tests.
(a) Trial Division. Write a function prime check trial(n) that checks if a given input integer n is a prime
number using trial division. Trial division simply checks, for a given input integer n, whether there is a
number between 2 and √
n that divides n. The function should take an int n and return a bool: True
if n is a prime, or False if n is not a prime.
1 def prime_check_trial ( n):
2 # WRITE YOUR CODE HERE
3 return # bool value ( True or False ) depending on prime or not
(b) Sieve of Eratosthenes. Write a function prime check sieve(n) that checks if a given input integer n is
a prime number using the Sieve of Eratosthenes. The function should take an int n and return a bool:
True if n is a prime, or False if n is not a prime.
1 def prime_check_sieve ( n):
2 # WRITE YOUR CODE HERE
3 return # bool value ( True or False ) depending on prime or not
(c) Fermat’s Little Theorem. Write a function prime check fermat(n) that checks if a given input integer
n is a prime number using the Fermat’s Little Theorem. Fermat’s Little Theorem states:
If p is a prime number, then for any integer a, the number a
p − a is an integer multiple of p.
The function should take an int n and return a bool: True if n is a prime, or False if n is not a prime.
1 def prime_check_fermat (n):
2 # WRITE YOUR CODE HERE
3 return # bool value ( True or False ) depending on prime or not
(d) Run your algorithms on the specified inputs in the main function to make sure your algorithm works.
You may modify the main function to try other numbers but make sure to change it back, and do not
turn in a modified main function.
Part D: Checking the Goldbach’s conjecture (1742)
As seen in class, the Goldbach conjecture is still not proven or disproven and can be stated as follows:
Every even integer greater than two can be written as the sum of two prime numbers.
(a) Write a function check goldbach(n) that verifies the conjecture for a given (potentially large) even
integer n sent as a parameter to the function. The function should return the two primes that sum
up to n, in the form of a list with two entries of type int. As before, make sure your return
types are correct, or your code will receive zero points. You may assume that your input will
be a positive even integer. Also note that Goldbach decompositions are not unique, so there may be
more than one correct answer for a given integer n (any satisfying sum will be correct). Hint: use your
function prime gen(n).
1 def check_goldbach (n):
2 # WRITE YOUR CODE HERE
3 return # two prime numbers that sum up to n
Page 3
(b) Run your algorithm on the specified inputs in the main function to make sure your algorithm works.
You may modify the main function to try other numbers but make sure to change it back, and do not
turn in a modified main function.
Page 4
