1.3. Primality Testing

Try these first

1. 1.

   Define a prime number.

   Hint

   Think about what factors a number can have.

2. 2.

   Is 4 a prime number? Why or why not?

   Hint

   Remember the definition of a prime number!

3. 3.

   What defines a prime number?

   • Only divisible by 1 and itself
   • Divisible by multiple numbers
   • Equal to 1

   Hint

   Recall the definition discussed.

4. 4.

   True or False: The GCD of 20 and 30 is 10.

   • True
   • False

   Hint

   Think about the factors of each number.

5. 5.

   Determine if 103 is a prime number using the naive testing algorithm. Demonstrate your process.

   Hint

   Remember to make your checks only go up to the square root.

6. 6.

   Explain how changing the input number affects the running time of the naive primality test.

   Hint

   Consider how each added bit may relate to the number of checks required.