A brute force approach is to divide n by each number from 2 to n-1 and if it is divisible then n is "Not Prime" else it is "Prime".
However, after √n no number divides n. Hence it is efficient to divide n by numbers from 2 to √n which reduces the number of operations.
Algorithm: Let n be an integer
Step 1: Initialize variable c = 2
Step 2: If c<=√n go to Step 3 else Step 5
Step 3: If n%c == 0 break and go to Step 5 else go to Step 4
Step 4: c = c+1 goto Step 2
Step 5: If c > √n then "Prime" else "Not Prime"
Example:
1) n = 6 , Integer(√6) = Integer(2.44) = 2
Step 1: c = 2
Iteration 1 :
Step 2: c<=2 i.e**.** 2 <= 2 go to Step 3
Step 3: n%c = 6%2 == 0 hence go to Step 5
Step 5: c = √n(2=2) then "Not Prime"
2) n = 17, Integer(√17) = Integer(4.12) = 4
Step 1: c = 2
Iteration 1 :
Step 2: c<=4 i.e**.** 2 <= 4 go to Step 3
Step 3: n%c = 17%2 != 0
Step 4: c = 2+1 = 3
Iteration 2 :
Step 2: c<=4 i.e. 3 <= 4 go to Step 3
Step 3: n%c = 17%3 != 0
Step 4: c = 3+1 = 4
Iteration 3 :
Step 2: c<=4 i.e. 4 <= 4 go to Step 3
Step 3: n%c = 17%4 != 0
Step 4: c = 4+1 = 5
Iteration 4 :
Step 2: Now c >=4 i.e. 5 >= 4 go to Step 5
Step 5: c > √n i.e. 5 > 4 then it is "Prime"
Time Complexity:
If n is the integer then the algorithm takes T(n) = O(√n) operations to determine whether the number is prime or not
Code: JAVA
