20-CS-472 Design and Analysis of Algorithms 2 Winter 2011
Prime Number Generator

Complexity, Divide-Conquer, Branch-Bound, Dynamic Programming, Backtrack, Linear Programming, Greedy, more

Instructions: Choose either Gen Prime to generate prime numbers or Test Prime to test one. In the case of Gen Prime enter a number of bits between 4 and 86 in the text field at the upper left. If this cannot be done, press the Try Again button first. Press Start to begin. Press Next to advance to the next step of the Miller-Rabin algorithm. Numbers to be tried as prime are displayed in the text fields labeled n:. When the Miller-Rabin test fails for a non-prime, that number will become red. Then, advancing to the next step results in a new number to be tried. If the number to be tried is prime, it will show yellow when the Miller-Rabin test has been applied, indicating it has passed the test. Then, advancing to the next step results in a new a: number and Miller-Rabin test. If the number is prime, it will never go red. The only way to generate a new number in that case is to press the Try Again button.

If Test Prime is selected the operation is the same except that the user must specify a number to try in the text field labeled n:.