Check if a number is prime. A number can have at most √n divisors. A small optimization can be made by observing all primes are of the form 6k ± 1. We can express any integer using the form 6k + i for i = -1, 0, 1, 2, 3, and 4.
We know the following is true:
- 6k + 0 is divisible by 2 or 3 since either of them divides 6 and 0.
- 6k + 2 is divisible by 2 since 2 divides 6 and 2 divides 2.
- 6k + 3 is divisible by 3 since 3 divides 6 and 3 divides 3.
- 6k + 4 is divisible by 2 since 2 divides 6 and 2 divides 4.
This leaves us with two integers which we need to check, 6k - 1 and 6k + 1 or 6k ± 1.
Best Case: Ω(1)
Average Case: θ(√n)
Worst Case: O(√n)
where n is the integer we want to check.
Worst Case: O(1)
Checks if an integer is prime. The function is_prime has the following parameter:
n: an integer which we want to check if it's prime or not
Return value: true if the number is prime, else false.
A single integer n.
1 or true if n is prime, else 0 or false.
11
1
15
0
1
0