We could use Finding Prime algorithm to test if a Number is Prime. However, too slow.
Therefore a probabilistic algorithm which test the Prime in random sequences according the theorems below:
Fermat Little Theorem: the remainder is A when number A's power of a Prime number is divided by this Prime number, e.g. A^P mod P = A
Chinese Hypothesis: 2^P mod P = 2
Euler Theorem: A^Phi(n) mod n = 1, Phi is the total number of the numbers ranging (1 to n-1) which has no common divisor, this total number is called coprime to n and denoted Phi(n), e.g. Phi(5) = 4, Phi(7) =6, Phi(9) = 6; if n is a Prime P, Phi(P) = P-1, therefore A^Phi(P) mod P = 1 or A^(P-1) mod P = 1;
Euler Criterion: A^((P-1)/2) mod P = +/- 1;
And we have Fermat, Miller–Rabin, e.g.