The World Of Algorithms
Compute the following using the improved version of Euclid’s algorithm.
(i)
(ii)
(iii)
(iv)
Assume that . Verify that divides and if and only if divides both and $m \bmod n,. $
Write an algorithm prime(n) to check if is prime.
Hint: A prime number has exactly two distinct factors, and . Can you make use of divisors(n) to write out prime(n)?
Write an algorithm primedivisors(n) to compute the list of divisors of that are prime numbers.
(Hint: Compute divisors(n) and then filter out the primes in this list.)
We can also find the of two numbers by computing the prime factorisation of both numbers. Try to write an algorithm to compute the prime factorisation of a number.
(i) The prime factorisation of is . How would you represent this?
(ii) How would you compare the prime factorisations of two numbers?