Get this book -> Problems on Array: For Interviews and Competitive Programming

Prime numbers hold a special place in the real world and determining if a number is a prime or not is an important algorithmic task.

Determining if a large number is prime or not is one of the most typical questions asked in the world of algorithms and competitive programming. There are several methods available to do this, but these can be broadly categorised into two:

**deterministic**algorithms**probabilistic**algorithms

Probabilstic algorithms determines if a number is prime or not with a high probability, but it is not 100% accurate. Deterministic algorithms can conclusively check if a number is prime or not, but typically requires much higher time complexity than probabilisitc algorithms.

One of the most popular probabilistic algorithm is based on **Fermat's little theorem**.

### Fermat's little theorem

**Fermat's little theorem** states that, for any prime number *n*, *a ^{n-1}mod(n) = 1* for

*1 â‰¤ a <n*.

For example, for **n=103**, if the randomly selected **a** is **73**, *73 ^{102} % 103* is equal to

*1*. This is true for any number between 1 and 103.

Since this condition can also be satisfied by non-prime numbers, we run this condition *k* times with a randomly selected *a* each time. The higher the value of *k*, the higher the accuracy.

### Pseudocode

```
Get N and set a value for k (more the value of k, the better)
for i from 1 to k
a = random(2, N-1) // get a random number between 2 and N-1
if (power(a, N-1) % N) != 1:
return False // not a prime (100% sure)
return True // N is a prime with high probability
```

### Complexity

Time complexity: **O(K log N)**

where N is the input number and K is the number of iterations

**log(n)** is the time complexity for computing *a ^{n-1}*, and the algorithm is repeated

*k*times, so the time complexity of this algorithm is

*O(klog(n))*.

### Example

For *n=103* and *k=4*,

**Pass 1:**

Let the randomly generated number be *99*

*99 ^{102}%103* = 1, satisfying Fermat's theorem.

**Pass 2:**

Let the randomly generated number be *28*

*28 ^{102}%103* = 1, satisfying Fermat's theorem.

**Pass 3:**

Let the randomly generated number be *57*

*57 ^{102}%103* = 1, satisfying Fermat's theorem.

**Pass 4:**

Let the randomly generated number be *12*

*12 ^{102}%103* = 1, satisfying Fermat's theorem.

Therefore, with a high degree of accuracy we can say that the number *103* is prime.

### Implementation

```
from random import randint
def pow(x, y, z):
num = 1
while y:
if y & 1:
num = num * x % z
y >>= 1
x = x * x % z
return number
def isPrime(n, k=10):
if n <= 1:
return False
if n <= 3:
return True
for i in range(k):
a = randint(2, n - 1)
if pow(a, n - 1, n) != 1:
return False
return True
if __name__ == "__main__":
if isPrime(103):
print("Prime")
else:
print("Not prime")
```

### Limitation

This test only completely fails in the case of **Carmichael numbers**

Carmichael numbers are composite numbers which satisfy Fermat's theorem. Hence, the Fermat primality test returns true for these numbers despite them being composite. There are **infinitely many Carmichael numbers**, with the smallest being **561**.

As numbers become larger, Carmichael numbers become increasingly rare. For all other numbers, provided a high enough value of **k**, it should return the correct answer with a high probability.