Suppose a primality testing algorithm always correctly answers "Prime" when its input is prime, but also says "Prime" with probability p when its input is composite. How large can p be for the algorithm to be useful?

To distinguish the input from the output, let "IP" denote the event that the input is prime and "IC" denote the event that the input is composite, while "OP" denotes the event that the output is "Prime" and "OC" denotes the event that the output is "Composite". In conditional probaility notation:

 P( OP | IP ) = 1 P( OC | IP ) = 0 P( OP | IC ) = p P( OC | IC ) = 1 - p

Suppose the proportion of primes to composites given as input to the algorithm is ( q : 1 - q ), so P( IP ) = q and P( IC ) = 1 - q (these are called "prior probabilities"), then

P( IP | OP ) = P( IP and OP ) / P( OP )
= P( IP ) * P( OP | IP ) / [ P( IP and OP ) + P( IC and OP ) ]
= P( IP ) * P( OP | IP ) / [ P( IP ) * P( OP | IP ) + P( IC ) * P( OP | IC ) ]
= q * 1 / [ q * 1 + ( 1 - q ) * p ]
= q / ( q + p - pq )

Similarly, P( IP | OC ) = q * 0 / [ q * 0 + ( 1 - q ) * ( 1 - p ) ] = 0