**Some theory**

A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself.

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31

One brute force is to loop through i:0->n : and find out if n is divisible by i. Complexity is O(n) here. But can we optimize it.

Yes. Here are the rules to find a prime number -

- Number has to be > 1
- Number cannot be even (Other than 2. 2 is prime). Because even numbers are always divisible by 2. This reduces the number to half.
- If you list out all of the factors of a number, the square root will always be in the middle. So when checking factors, we need not check 0 to n. Check only upto square root of n, that should cover all possible factors. This further reduces the comparisons to sq. root of n, and that too excluding all evens.

**Java Code**

package main.java.algo; public class IsPrime { // if you list out all of the factors of a number, the square root will always be in the middle public static void main(String[] args) { System.out.println(Integer.valueOf('c')); } // checks whether an int is prime or not. boolean isPrime(int n) { //prime is natural number greater than 1 if(n <= 1) return false; // but ignore 2, as 2 is a prime number if(n == 2) return true; // check if n is a multiple of 2 if (n % 2 == 0) return false; // if not, then just check the odds : note -> i += 2 // check only upto square root of a number for (int i = 3; i * i <= n; i += 2) { if (n % i == 0) return false; } return true; } }