heuristics - is N a prime number?

Question

I read a positive integer N from the stdin and I'm trying to figure out if N is a prime number.

I know I can divide N to all the positive numbers up to sqrt(N), but that's time consuming and my algorithm affords to give false positives from time to time so I'm looking for an heuristic to solve this.

I remember I learned about an algorithm in collage last year that would pick a number, then check if N is divisible by that number (or it's factors) and if not, then it could tell N is a prime, but it would falsely identify it as prime about 1/40 of the time.

Does anyone recognize this algorithm I'm talking about? A link to it would be very helpful.

Answer 1

Well, there are a few probabilistic algorithsm, some described in the wikipedia page, most likely you are speaking about Miller-Rabin Fermat Primality Test

Note that since 2002 there is actually a O(log(n)^6) deterministic approach to determine if a number is prime - called AKS (after its developers)¹

---

It is an interesting issue - many thought that primality test cannot be done both polynomially in the size of the input (i.e. logarithmic in n) and both deterministically, but their approach showed otherwise.