Previous posts on primality testing are all trying to factor the input number. For a very large number with few hundreds of bits, it is difficult to compute in that manner.
This post introduce a probabilistic approach based on Fermat’s primality test.

Fermat’s Little Theorem

Fermat’s primality test is based on Fermat’s [...]

The previous two posts cover the naive approaches for primality testing and a method with precomputation. This post introduces a new method which could perform better than previous approaches and it can be used together with the precomputation.

The optimization is based on the observation that all prime numbers are in the [...]

Previous post covers two naive methods for primality testing. This post introduces an algorithm to generate prime numbers called Sieve of Eratosthenes. With this algorithm, an optimization can be applied to speed up the primality testing.

Sieve of Eratosthenes

Suppose we want to generate prime numbers up to N. The algorithm consists of two [...]

Primality refers to determining if a given input number is prime or not. This post covers two naive approaches for primality testing.

Naive Approach 1

This most straightforward approach is to check if a given input integer n is divisible by integers from 2 to n-1. If a number is prime, then it should not [...]