Math 218-Lab0

Purpose: To recall some of the basics of C++ and practice some run time analysis + to consider one of the most important (and difficult!) problems in Number Theory and in some more practical fields: PRIMALITY. In fact, determining whether a given number is prime or not is of great theoratical AND practical importance. For instance, this is one of the most fundamental problems in cryptography. There have been lots and lots of research on this problem. Very recently, a deterministic, polynomial time algorithm has been discovered. This is considered to be a breakthrough in the area. You can read more about it, including the full paper here.

What to do? Write a program which includes the following

• An implementation of the function IsPrime as described in the class. The prototype of this function is
  • bool IsPrime( int )
  • Provide preconditions and postconditions for this function. (And as usual, provide necessary documentation throughout your program).
• Make sure you test the function and you are confident that it works correctly
• Use this function to find and print out -both to the screen and to a file in your class directory (call it Lab0output.cpp)- first 1000 primes. Leave a space between the numbers.
• Again use this function to find number of primes between 10^5 and 10^6. Write your program so that it can easily be modified to find number of primes between N and 10*N for any choice of a positive integer N (use a constant variable)
• What is the worst-case running time of IsPrime as a faunction of its argument n? Express your answer in Big-O notation (without any unnecessary constants). How about best case running time? It is standard to consider the running time of an algorithm (or program) in terms of number of digits in binary. What is the worst-case running time of IsPrime as a function of number of digists of its argument? Is it a polynomial? Turn in your running time analysis as a hard copy in class on Wed, 1/22.