is_prime

Checking Whether a Number is Prime or not

A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example, 5 is prime because 1 and 5 are its only positive integer factors, whereas 6 is composite because it has the divisors 2 and 3 in addition to 1 and 6. There are many algorithms to check primality. Here trial division algorithm is implemented.

Run time analysis

T(n) = Θ(sqrt(n))

Formulation of the problem

Let n be a natural number. Primality means:

• n has only two positive divisors 1 and itself.