 Is a Number Prime?
This function returns 1 if a number is prime; otherwise, it returns 0.
A prime number has only two divisors: 1 and itself. (The number 1 is not prime.)
The function is only required to work correctly on positive numbers and 0. The efficiency of the function, or lack thereof, is not the bug.
Source Code
1. def isPrime( number ):
2. """ Check if a number is prime
3.
4. number: An integer.
5.
6. Returns: 1 if number is prime, 0 otherwise
7. """
8.
9. """ Special-case 0 and 1, which are not prime.
10. """
11.
12. if ( number == 0 ) or ( number == 1):
13. return 0
14.
15. """ Make a range of all numbers up to half of the
16. one we want to check
17. """
18.
19. checkList = range(2, (number/2))
20.
21. """ If we find a factor, return 0 right away.
22. If the loop ends first, then it is prime.
23. """
24.
25. for check in checkList:
26.
27. if ((number / check) * check) == number:
28. return 0
29.
30. else:
31.
32. return 1
Suggestion
On line 12, an if statement has a logical or in it. Because it can be easy to accidentally invert the meaning of these, check that this line is correct. The main part of the algorithm is the loop that starts on line 25. Does the loop counter look like it is used correctly? Are the return statements correct? Ensure that the function follows the behavior it is defined to use (that is, make sure that it has not swapped when it is supposed to return 0 and when it is supposed to return 1). What set of inputs do you need to choose to ensure that every line of code in the function is covered?
Hints
In an algorithm such as this, it's likely that any errors appear near the limit, which in this case, is with small numbers. Walk through the code with the following values for the number parameter to the function:
Test the introductory special case: Try number equal to 0 and 1. Test the main logic with a mix of small prime and non-prime numbers: Try number equal to 2, 3, 4, 5, and 6.
Explanation of the Bug
The code on line 19 that creates the range of numbers to check
checkList = range(2, (number/2))
is incorrect in the case where number is equal to 4. Recall that the list returned by range() does not include the end point; therefore, range(2, 2) is an empty range. As a result, when number is 4, the for loop on line 25 immediately falls through to the else statement on line 30 and then to the return statement on line 32, and the code incorrectly reports that 4 is a prime number. It works correctly on all other positive numbers. This is a D.limit error because it fails only at the edge of the range of possible values.
The fix is to extend the checkList range created on line 19 by one more element, so in the case of number equal to 4, the for loop on line 25 will iterate once with a value of 2:
checkList = range(2, (number/2)+1)
The smallest value of number that isn't special-cased by the introductory code is 2; you can quickly verify that when number is 2 or 3 the checkList range will be initialized to (2,2) on line 19, meaning the for loop on line 25 never iterates and the function properly returns 1 on line 32.
|
