How to Check Prime Number in JAVA?

Any natural number that is divisible only by itself and 1 is called a prime number in Java. In other words, prime numbers have just two factors i.e. 1 and number itself.

Examples: 2, 3, 5, 7, 11, 13 …… . All natural numbers other than 1 and prime numbers are called composite numbers.

Prime numbers exhibit a number of odd mathematical properties that make them desirable for a wide variety of applications, many of which belongs to the world of information technology. For example, primes find use in pseudorandom number generators and computer hash tables.

There are several instances in the history of using encryption for hiding information in plain sight. Amazingly, it is the process of using prime numbers to encode information.

With the introduction of computers, modern cryptography was introduced. It became feasible to generate complex and longer codes that were much, much difficult to crack.

Most modern computer cryptography is dependent on making use of prime factors of large numbers. As prime numbers are the building blocks of whole numbers, they are of the highest importance to number theorists as well.

So the main Question was how to check if a number is prime in Java and how we find a prime number in Java.

Some facts about prime number are:

• 2 is the only even number that is prime.
• Every even number which is greater than 2 can be written as the sum of 2 prime numbers.
• There are only 2 numbers which are prime and consecutive which are 2 and 3.

Algorithm for Prime Number Program in Java

• Check if the input number (N) is 1. If it is 1, it is neither prime nor composite. Still, it is not prime so we will print “NO”
• Else, iterate from 2 to N-1 and check if any number is able to divide the number N completely i.e. if any number from 2 to N-1 is a factor of N. If we find even one number that is a factor of N, N will not be a prime number as we would have a number apart from 1 and N that divides N completely. So, in this case, also, print “NO”
• Finally, if we have iterated from 2 to N-1 and have not found any factor of N, this means that N is only divisible by 1 and N itself. So, it is a prime number. Hence, print “YES”

Check out My Latest post on Developer Helps for some Interesting Insights

Program to check Prime Number in Java using for loop

If any number greater than 1 divides the number, the number is not prime. Observe that there cannot be any divisor of a number n greater than n/2. Hence, we can divide the number n with only those natural numbers which are less than or equal to n/2. If we cannot find any factors less than or equal to its half, n must be a Prime Number Program in Java

public class DeveloperHelps {
public static void main(String[] args) {
int number = 13;
boolean flag = false;
for(int i = 2; i <= number/2; ++i) {
if(number % i == 0) {
flag = true;
break;
}
}
if (!flag)
System.out.println(number + " is a prime number.");
else
System.out.println(number + " is not a prime number.");
}
}

Run Code >>

The output of the program will be:

13 is a prime number. 

When we are checking inside for loop, we check if the number is divisible by any other number by dividing it by 2. If it is divisible, we get the output as true. As a result, the number is not a prime number. As a result, the value is false and the number is a prime number.

Complexities:

Time Complexity:

O(n) since the loop iterates for n/2 times and O(n/2) = O(n).

Space Complexity:

O(1), since only constant space is being used

Program to Check Prime number in Java using a while loop

This program is created using the while loop. Also, the program is modified in a way that it will print the number along with a message saying whether it is prime or not. Let’s have a look at the program given below:

In the while loop, the loop will run until i<= number/2. We will check if the number is divisible by i in each iteration. And the value of i will keep incrementing by 1.

public class DeveloperHelps {
public static void main(String[] args) {
int number = 13, i = 2;
boolean flag = false;
while(i <= number/2)
{
if(number % i == 0)
{
flag = true;
break;
}
++i;
}
if (!flag)
System.out.println(number + " is a prime number.");
else
System.out.println(number + " is not a prime number.");
}
}

Run Code >>

The output of the above program will be:

13 is a prime number.

Complexities:

Time Complexity : O(n) since the loop iterates for n/2 times and O(n/2) = O(n)

Space Complexity: O(1), since only constant space is being used

https://www.facebook.com/developerhelps/

https://www.developerhelps.com/contact/