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

#### Program logic:

If any number which is not divisible by any other number which is less than or equal to square root of that number, then it is prime number.

Lets create java program for it:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
package org.arpit.java2blog; public class PrimeNumberMain { public static void main(String[] args) { System.out.println("17 is prime number?: "+isPrime(17)); System.out.println("2 is prime number?: "+isPrime(2)); System.out.println("91 is prime number?: "+isPrime(91)); System.out.println("29 is prime number?: "+isPrime(29)); System.out.println("81 is prime number?: "+isPrime(81)); } public static boolean isPrime(int number) { for (int i = 2; i <=Math.sqrt(number); i++) { if(number%i==0) return false; } return true; } } |

Run above program, you will get following output:

1 2 3 4 5 6 7 |
17 is prime number?: true 2 is prime number?: true 91 is prime number?: false 29 is prime number?: true 81 is prime number?: false |

Please go through java interview programs for more such programs.

You can make this algorithm 2 times faster skipping division by even numbers:

for (int i = 2; i <=Math.sqrt(number); i+= (i>2 ? 2 : 1)) {

…

}