Prime Numbers
We will discuss three approaches for determining if a number is prime or not. We will start with the worst time complexity approach to the best time complexity approach.
Approach 1:
A number is a prime number if it has no other factors other than 1 and the number itself. For Ex: 11 is a prime number because it is not divisible by any other number than 1 and 11. To determine if any number (N) is prime or not, we need to iterate each number (except 1 and N) before N and have to check if the modulus of that number with N is 0 or not, because if the modulus if 0 then that means that number is a factor of N and in that case, N is not a prime number.
1 2 3 4 5 6 7 8 9 10 | public static boolean isPrimeWorst(int N) { if (N <= 1) { return false; } for (int i = 2; i < N; i++) { if (N % i == 0) return false; } return true; } |
Approach 2:
The issue with the first approach is that we need to iterate each and every
number before N to determine if N is prime or not and say if N is a big number
then it will take a lot of time to execute the programme.
If we observe
closely, we will get to know that if we do not have any factors of N till the
square root of N, then definitely there will be no factors after that. In that
case what we can do is we can check for each number till Math.sqrt(N) to check
if any number is divisible by N of not, and then we can determine if N is
prime or not.
1 2 3 4 5 6 7 8 9 | public static boolean isPrimeMedium(int N) { if (N <= 1) return false; for (int i = 2; i <= Math.sqrt(N); i++) { if (N % i == 0) return false; } return true; } |
Approach 3:
While the second approach is better than the first one, we can still improve our solution.
One rule of Mathematics is every prime number can be written in the form of 6K+1 or 6K-1 except 2 and 3. Which means we can break each prime number in the form of 6K+1 or 6K-1. For Example, 5 can be written as [6*1 – 1] or 17 can be written as [6*3 – 1]. But the vice versa is not true.
Taking this rule into consideration we can use the below code to find if a number is prime or not.
1 2 3 4 5 6 7 8 9 10 11 12 13 | public static boolean isPrimeBest(int N) { if (N <= 1) return false; if (N <= 3) return true; if (N % 2 == 0 || N % 3 == 0) return false; for (int i = 5; i <= Math.sqrt(N); i = i + 6) { if (N % i == 0 || N % (i + 2) == 0) return false; } return true; } |
In here, what we are doing is we are returning false if number is 1 and we are returning true if number is 2 or 3 in the first two if conditions.
Further, if any number is divisible by 2 or 3 (except 2 and 3 as if N is 2 or 3, we have already returned true in line 5) then it is definitely not prime. Hence we will return false.
Now for the rest terms, we can run a loop starting 5 till square root of N, and every time we can increase the loop by 6 times. This will reduce the number of checks to a great extent.