JavaScript is disabled for your browser. Some features of this site may not work without it.
Some Negative Results Concerning Prime Number Generators

Author
Pritchard, Paul
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.
Date Issued
1983-02Publisher
Cornell University
Subject
computer science; technical report
Previously Published As
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR83-542
Type
technical report