Prime Number: A prime number is an integer greater than 1,which can be divisible by 1 and itself.
Examples: 2, 3, 5, 7, ...
Brute-force approach:
We need not to check even numbers as they never be prime numbers except 2. So we are returning false for even numbers and numbers less than 2 and testing divisors for only Odd numbers.
And also we are skipping even divisors as non of the odd numbers will have an even number as a divisor.
/**
* This program is to find a number is prime or not
* @author Technical Explorer
*/
package com.technicalexplorer;
import java.util.Scanner;
public class PrimeNumber {
public boolean isPrime(int number) {
boolean isPrime = true;
/**
* return true if number is 2 as it is
* the only even number which is also prime.
*/
if(number == 2) {
return isPrime;
}
//return false if number is less than 2 or even number
if(number < 2 || number%2 == 0) {
return !isPrime;
}
/**
* Skipping even divisors as an odd number can't
* have even divisors.
*/
for(int i=3; i<number; i=i+2) {
if(number%i == 0) {
//returning false as number is divisible by i
return !isPrime;
}
}
/**
* returning true as number has no positive
* divisors other than 1 and itself
*/
return isPrime;
}
public static void main(String[] args) {
//Scanner is for get number from user
Scanner scanner = new Scanner(System.in);
PrimeNumber primeNumber = new PrimeNumber();
System.out.print("Please enter number: ");
int number = scanner.nextInt();
//If there is no use of scanner then close it.
scanner.close();
if(primeNumber.isPrime(number)) {
System.out.println(number + " is a Prime Number");
} else {
System.out.println(number + " is not a Prime Number");
}
}
}
Sample Input and Output
1. Input: Please enter number: 131
Output: 131 is a Prime Number
2. Input: Please enter number: 1244
Output: 1244 is not a Prime Number
Brute-force - Optimized
In this technique, we just have to check divisors till half of the given number because if there is no divisor till half of the given number then no possibility of having divisor between number/2 to number. Below is the method with implemented the same.
public boolean isPrimeOptimized(int number) {
boolean isPrime = true;
/**
* return true if number is 2 as it is
* the only even number which is also prime.
*/
if(number == 2) {
return isPrime;
}
//return false if number is less than 2 or even number
if(number < 2 || number%2 == 0) {
return !isPrime;
}
//Checking for divisor till half of the given number
number = number/2;
for(int i=3; i<=number; i=i+2) {
if(number%i == 0) {
//returning false as number is divisible by i
return !isPrime;
}
}
/**
* returning true as number has no positive
* divisors other than 1 and itself
*/
return isPrime;
}
Efficient Approach
Actually we need not to check for divisors till number/2, instead we can check till square root of number because if a number is not a Prime then it must have at least one divisor which is less than or equal to square root of that number.
public boolean isPrimeEfficient(int number) {
boolean isPrime = true;
/**
* return true if number is 2 as it is
* the only even number which is also prime.
*/
if(number == 2) {
return isPrime;
}
//return false if number is less than 2 or even number
if(number < 2 || number%2 == 0) {
return !isPrime;
}
/**
* Checking for divisor till square root of
* the given number + 1 in case number is
* round off'd while finding square root.
*
*/
number = (int)Math.sqrt(number);
for(int i=3; i<=number; i=i+2) {
if(number%i == 0) {
//returning false as number is divisible by i
return !isPrime;
}
}
/**
* returning true as number has no positive
* divisors other than 1 and itself
*/
return isPrime;
}
If I missed anything please comment below.
All the very best!!
