Some Negative Results Concerning Prime Number Generators

Abstract

Programs due to Wirth and Misra for generating the prime numbers up to a specified limit are investigated. It is shown that Wirth's program is incorrect according to three increasingly weak criteria, and a composite number is exhibited that the program accepts as prime. This is the smallest known counter-example, and could not have been found by the usual method of program testing - the program would run for trillions of years on the fastest computer before reaching it! Closely related counter-examples are given to a conjecture of Misra concerning his program.