8.4. Naive Algorithm for Primality Testing

Try these first

1. 1.

   What defines a prime number?

   Hint

   Think about the definition and the number of divisors.

2. 2.

   Is the number 4 prime or composite?

   Hint

   Consider the divisors of 4.

3. 3.

   What is a prime number?

   • A number with more than two factors.
   • A number with only two factors.
   • A number that is always odd.

   Hint

   Recall the definition of a prime number.

4. 4.

   The naive algorithm for primality testing uses which of the following methods?

   • True
   • False

   Hint

   Think about how we identify potential factors.

5. 5.

   Apply the naive algorithm to test whether 49 is a prime number. Show your steps.

   Hint

   What numbers will you check against 49?

6. 6.

   How many checks would you need to determine if 101 is prime using the naive method?

   Hint

   Determine how many divisors you check.