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.
T(n) = Θ(sqrt(n))
Let n be a natural number. Primality means:
- n has only two positive divisors 1 and itself.