How To Check Prime Number with Java

Prime number is a natural number greater than 1 and only divisible by 1 or itself, i.e. a prime number has only two factors, 1 and itself. The number 2 is the smallest and only even prime number. 1 is excluded as a prime number.
In order to check if a number is prime we should find if there is any divisor other than 1 or itself. We can find this by dividing the number(say n) by each number between 2 and n-1. For e.g. in order to check if 13 is a prime number, we need to check if 13 is divisible by 2 through 12. If remainder is 0 for any one division then the number is not prime.

Trying a number n by all numbers between 2 and n-1 is very time consuming, and luckily we have a faster approach. It is only necessary to test the factors between 2 and the square root of n in order to check a prime number.
For e.g. if n=61, we need to test only the numbers between 2 and sqrt(61).
sqrt(61) = 7.
61 is not evenly divisible by 2,3,4,5,6,7, so 61 is a prime number.

Again, to further save time, we can test with only the prime factor from the list(2,3,4,5,6,7). For e.g. in the list (2,3,4,5,6,7), we should try with only the prime numbers 2,3,5,7.

Sample Java program to check if a number is prime and print all prime numbers up-to the number:

package com.examples;
import java.util.Scanner;

public class PrimeNos {

 public static void main(String[] args) {
  Scanner in = new Scanner(System.in);
  System.out.println("Enter a number to check prime: " );
  int n = in.nextInt();
  if (checkPrime(n))
   System.out.println("Number is prime");
  else 
   System.out.println("Number Not prime....");
  
  System.out.print("The prime numbers till " + n + ": ");
  for (int i=2; i<=n;i++){
   if (checkPrime(i))
    System.out.print(i + " ");
  }
 }
 
 public static Boolean checkPrime(int n) {
  int sqt = (int) Math.sqrt(n);
  for (int i=2; i<=sqt; i++) {
   Boolean test = checkPrime(i); //save more time, use only prime factors
   if (test) {
    int result = n % i;
    if (result == 0){ 
     return false;
    }
   }
  }
  return true;
 }
}

Output:

Enter a number to check prime: 29
Number is prime
The prime numbers till 29: 2 3 5 7 11 13 17 19 23 29