### Primality Test

Primality test is a test to determine whether a number is prime or not. There are many different primality tests.

Time complexity: \(O(\sqrt{n})\)

Related: Sieve of Eratosthenes

## What is a prime number?

A number is prime if it has exactly two positive whole number divisors,

*one and itself*. On the other hand, a number is composite if it has more than two positive whole number divisors. Some interesting facts about prime numbers are: one is not a prime number since it does not satisfy the definition of being a prime, and there exist no even primes greater than 2.## Now, let's look at the naive approach

To find if a number n is prime we could simply check if it divides any numbers below it.

Time complexity: \(O(n)\)

Time complexity: \(O(n)\)

## The better approach

- We only need to check divisibility for values of i that are less or equal to the square root of n
- Since, there exist no even primes greater than 2. Therefore, after checking n is not an even number we can safely increment the value of i by 2 to avoid dividing n by odd numbers.

Time complexity: \(O(\sqrt{n})\)

Related: Sieve of Eratosthenes

## Comments

## Post a Comment