Pomerance and Lenstra improved the exponent to six in the first polynomial-time algorithm for this problem, which was announced in a 2002 paper by Agrawal, Kayal, and Saxena titled "[this problem] is in P." False positives in this problem include the Carmichael numbers.
An algorithm for this problem that classifies bases as either witnesses or liars is named for Solovay and Strassen. The Baillie–PSW algorithm works because the lists of exceptions to two other criteria have no known overlaps. Pomerance and Lenstra improved the exponent to six in the first polynomial-time algorithm for this problem, which was announced in a 2002 paper by Agrawal, Kayal, and Saxena titled "[this problem] is in P." False positives in this problem include the Carmichael numbers. A naïve approach to this problem is to divide the input by every positive integer less than it, looking for a remainder of zero. For 10 points, identify this problem of determining whether a given integer has exactly two positive divisors.
An algorithm for this problem that classifies bases as either witnesses or liars is named for Solovay and Strassen.
primality tests [accept PRIMES; accept anything about determining if a number is prime] &lt;Thompson&gt;