Task 1: Write a function isprime(n) that tests if n is prime by trial division up to sqrt(n). This function should return True or False. You can get the square root function in python by importing with from math import sqrt and calling sqrt(n). Test your code for n up to 20.

Task 2: Write a function fermattest(n, a=2) that returns True if n is a Fermat pseudoprime (with respect to a, default: a=2), and False otherwise. Code the Fermat primality test with your function modexp(a,n,m) using repeated squaring from Lab 5. Test your code for n up to 20, and n = 341 (the first non-prime pseudoprime for a=2). Is 341 pseudoprime with respect to a=3 or a=5?

Task 3: Write a function countpseudoprimes(n) which prints out the number of primes and pseudoprimes up to n, and the probability that a pseudoprime is not prime. (Here by pseudoprime we mean Fermat pseudoprimes with respect to 2.) Try to make your algorithm as efficient as possible. Run this function for n = 1000, 10000, 100000 and 1000000. (You should gather 2 things from your findings---there are lots of primes and pseudoprimes are almost always prime.)

Task 4: Write a function MRtest(n, a=2) to implement the Miller-Rabin primality test.

Task 5: Write a function countMRpseudoprimes(n) to do the same as Task 3 for Miller-Rabin pseudoprimes (with repsect to a=2).