Recall that prime numbers are those that are only divisible by 1 and themselves. They play a significant role in computer cryptography where they help to form computationally hard problems.
We would like to find all of the prime numbers less than or equal to a value n. We will do so by making two functions. One that decides if a given number is prime and a second that counts the primes up to n.
Let us start with the isPrime function. We will need to test it with a variety of numbers. We want to test it with some numbers that are prime and some that are not. 3, 7, 17, and 23 are all prime numbers. 4, 15, and 181 are not. We will also test it with 1 and 2, which are special cases. 1 is not prime (prime numbers should have 2 factors), and 2 is the only even prime number.
To test if a number n is prime, we need to see if anything in the range 2 to n - 1 can divide into it. The starter code has a counting loop that is missing some pieces (marked with ???). Fill in the blanks so that the loop counts from 2 to n - 1.
Don’t worry about passing the tests yet, just look at the program output and verify that the loop is iterating the correct number of times. Make sure your counter does not go all the way to n or stop at n - 2.
Now let’s check if the current value of the loop counter divides into n. Recall that if n is divisible by i, then n % i will be 0. Add a conditional to check if i divides into n. If so, print out "NOT A PRIME!".
If you find a factor, there is no point continuing on with the loop - we know that n is not prime. One way to handle this would be to use break to stop if we find a factor. We would need a variable to keep track of if we think the number is prime. Initially, we would assume it is. If we find a divisor we would change our mind. Here is pseudocode for that approach:
isPrime = true
loop from 2 to n - 1
if n is divisible by i
isPrime = false
break
return isPrime
Another way would be to simply return false; as soon as we find the factor. This approach would have the advantage of not needing a variable to keep track of our answer.
We still have a problem with the special case. Our loop never runs if n is 1. So we end up returning true. Sometimes the best way to deal with a special case is to just add logic to handle it. Add a condition that returns false if n == 1. This logic could go either before or after the loop.
Now remove all the cout statements. They were helpful for testing and debugging your code, but will not be needed or wanted in the final version of the function. Make sure you still pass all the tests!
Subsection8.13.4Understanding countPrimes and Tests
Count primes needs to check each value from 1 to n to see if it is prime. Consulting the internet to find a list of prime numbers, it appears that there are 2 primes less than or equal to 4, 4 primes less than or equal to 10, and 25 primes less than or equal to 100. A tricky case for this problem might be right at a number that is prime. 11 is the 5th prime, so let’s include it as a test case:
Count primes needs to check each value from 1 to n to see if it is prime. Fortunately, we now have isPrime to do the checking for us. We will need an accumulator to keep track of how many primes we have seen. The guide below will help you build out the needed code in the exercise below.
Let’s start in on the rest of the code for countPrimes. We know we need to count from 1 to n. Write a loop that does that and prints out each value. Don’t worry about checking primes or passing the tests. Just make sure the loop counts through he right numbers.
Try testing each number that your loop counts through by calling your isPrime function and passing it the current number. If isPrime returns true, print out "Prime".
You now hopefully have a working countPrimes function. At this point, building a main function to get some input and print out the final result is easy. Here is such a program. If you want, you can paste in your functions from the exercise above to try it out:
This case study previews some of the advantages of doing iterative development - building and testing one piece of a program at a time. We will learn more about solving complex problems by breaking them down in a future chapter.
It also demonstrates the advantages of building abstractions - wrapping complex logic into a function like isPrime so that you don’t have to worry about those details when you just want to know “is this number prime?”.
Instead of writing that function, we could have written the logic for isPrime into countPrimes. That would involve a nested loop where the outer loop counted i from 2 to n and the inner loop counted from 2 to i, checking to see if any value divides into i. Although that would work, it would be more complex to build and debug. Making the
Our functions aren’t very efficient. There are some tweaks we could make to speed them up (for instance, there is no point in checking values larger than \(\sqrt{n}\) to see if they are factors, so we could stop the isPrime loop at that point). But there are much faster algorithms for determining if values are prime. So if efficiency was a big concern, we would be better off going back to the drawing board than trying to improve this algorithm.
