Prime Number in Java

Have you ever thought about how to check if a number is prime using Java? What makes a number prime, and why is 2 so unique? How can we write efficient Java programs to find prime numbers? From basic loops to optimized logic like the square root of n, Java offers many ways to solve it. Why are prime numbers so important in the real world, like security and encryption?

In this guide, we will answer all these questions and see the different methods to check prime numbers in Java.

Table of Contents:

• What are Prime Numbers in Java?
  • Properties of Prime Numbers
• How to Write a Prime Number Program in Java
  • Method 1: Simple Program to Check Prime using Iteration
  • Method 2: Optimization by n/2 iterations
  • Method 3: Optimization by Square Root
  • Method 4: Basic Recursion Technique
  • Method 5: Prime Number Program Using Count
  • Method 6: Prime Number Program Using Method in Java
  • Method 7: Prime Number Program Using a Flag Variable
• Prime vs Composite Numbers
• Prime Numbers in Real-world Applications
• Conclusion

What are Prime Numbers in Java?

A prime number is greater than 1 and has no positive divisors other than 1 and itself (i.e., it is only divisible by 1 and itself).

Note: The number 1 is not a prime number, and 2 is the smallest and only even prime number.

For example,

Properties of Prime Numbers

1. A prime number has only 2 factors: 1 and itself.
2. 1 is not a prime number.
3. 2 is the smallest and only even prime number.
4. All other prime numbers are odd numbers.
5. Prime numbers are infinite.
6. Prime numbers greater than 2 are odd.

Master Java Today - Accelerate Your Future

Enroll Now and Transform Your Future

Explore Program

How to Write a Prime Number Program in Java

There are various methods to check whether a number is prime in Java. Some of them are as follows:

Method 1: Simple Program to Check Prime using Iteration

In this method, different iterative methods like for-loop and while-loop are used to check whether a number is a prime number or not.

1. For Loop

This method checks whether a given number is prime or not using a for loop. The for loop will start from 2 to n-1, where n is the range. If any number divides it exactly, it’s not prime, and if no such number divides it, it’s prime.

Example:

Output:

Explanation: In the above Java code, the number 17 is checked as a prime number. After the for loop, the if-else statement is used, which returns a boolean value.

2. While Loop

This method checks whether a given number is prime or not using a while loop. A while loop repeats a block of code as long as a condition is true. The while loop will start from the variable i=2 to the condition i<n, where n is the range. If (n % i == 0) is true, this means i divides n, hence it is not a prime number

Example:

Output:

Explanation: In the above Java program, the while loop is used, which checks each number for the divisibility of i and then increments it by one. If the number is divisible by any of the values of i, then the while loop breaks and a boolean value is returned.

Method 2: Optimization by n/2 iterations

In this method, the loop only goes to n/2 iterations, instead of n-1, because we know that a number cannot divide any number greater than half of itself, except itself. So, we only need to check up to n / 2. If n is divisible by any number greater than n/2, then the other factor would be less than n/2 and would have already been checked.

For example, let us consider the number 20. First, check the divisors from 2 to 20/2, i.e., 10, and 20 % 2 is 0, which is not prime, hence no need to go beyond 10.

Example:

Output:

Explanation: In the above Java program, instead of iterating all the way to n, the result can be found by iterating till n/2.

Method 3: Optimization by Square Root

In this method, instead of iterating the loop to n/2, the loop iterates to only the square root of n to reduce the number of checks to only the square root of the number. If the number n is not prime, it can be factored as n = a × b, and at least one of its factors, a or b, will be ≤ square root of n. So if no number from 2 to √n divides n, it must be prime.

For example, check if 29 is prime. The square root of 29 is approx 5.38 hence, we will check only up to 5, and since none of the numbers 2, 3, 4, or 5 divide 29, it is a prime number.

Example:

Output:

Explanation: In the above Java program, instead of iterating till n/2, the answer can be found by iterating till the square root of n.

Method 4: Basic Recursion Technique

In this method, we will check if a number is prime using recursion, instead of using loops. Recursion is a technique in which a method calls itself to solve a problem. In this method, we create a function that tests if the number is divisible by any number from 2 up to the square root of n. If any number divides it, it is not a prime number, and if no number divides it, it is a prime number.

Example:

Output:

Explanation: In the above Java program, the function isPrime(int n, int i) has a return type of boolean, and two base cases, i.e, if n<=1, then the number is not prime, and if i exceeds the square root of n, then it is prime.

Method 5: Prime Number Program Using Count

This method is used to count how many numbers divide the given number n and use it further to determine whether it is prime or not. A prime has only divisors, 1 and the number itself. So the logic is that, start from 1 and go up to n, then count how many numbers divide n, i.e., n% i == 0. If the count is 2, the number is prime, else it is not prime.

For example, check if 7 is prime:

7 % 1 = 0 , count++

7 % 2 ≠ 0

7 % 3 ≠ 0

7 % 4 ≠ 0

7 % 5 ≠ 0

7 % 6 ≠ 0

7 % 7 = 0, count++

The count is increased to 2, hence 7 is a prime number.

Example:

Output:

Explanation: In the above Java program, the variable starts from the value 0 and then goes to n. The count variable increases when n%i==0, the number is prime if the count==2, and hence the output is printed.

Method 6: Prime Number Program Using Method in Java

In this method, a method is made that checks whether the number is prime or not. Then it is called in the main method, and the parameter is passed to it. This method uses a simple loop to check for prime numbers, avoiding recursion for better performance in larger inputs.

Example:

Output:

Explanation: In the above Java program, a function isPrime(int n) is created that takes n as a parameter and returns a boolean value. It checks the divisibility of a number from 2 to the square root of n. If any divisor is found, it returns false; if the loop completes with no divisor, it returns true.

Method 7: Prime Number Program Using a Flag Variable

A flag variable is a variable that is used to indicate whether a condition has been met or not. In the case of checking a prime number, we use a flag variable, which can be like boolean isPrime or an int flag = 0. Now, let us assume that the given number is prime. If we find any number that divides it, we set the flag = 1 or isPrime = false. At the end, we check the flag to decide if the number is prime or not.

Example:

Output:

Explanation:

In the above Java program, first, the flag variable is set to 0, assuming it to be prime. Now, further, if any divisor is found in the loop, the flag value is changed to 1, and the loop breaks down.

Prime vs Composite Numbers

1. Prime Numbers

A prime number is a natural number that is greater than 1 and has exactly two factors, 1 and the number itself.

For example:

2, 3, 5, 7, 11, 13, 17, 19, 23, …and so on.

Note: 2 is the only even prime number

2. Composite Numbers

A composite number is a natural number that is greater than 1 and has more than two factors.

For example:

4 has 3 factors, 1, 2, and 4, and 6 has 4 factors, 1, 2, 3, and 6.

Further, 8, 9, 10, 12, 15, 20, …and so on are composite numbers.

Here is the key difference between prime numbers and composite numbers

Prime Numbers in Real-world Applications

Prime numbers are used in many real-world applications. Some of them are

1. Cryptography & Cybersecurity

Many algorithms, like the RSA algorithm, use prime numbers to secure the data, in which two large prime numbers are multiplied to generate a public key, and the original prime numbers are used for the private key.

2. Computer Algorithms & Hashing

Hashing functions that are used in databases, compilers, and search engines use prime numbers to avoid collisions.

3. Secure Communication Channels

Prime numbers allow end-to-end encryption, which is used in many applications like WhatsApp, Telegram, etc.

4. Music and Sound Engineering

Some sound waves and rhythm patterns are based on prime intervals to create unique and non-repetitive beats.

5. Coding Theory and Error Detection

Primes are used in coding theory to build systems that detect and correct errors (e.g., QR codes, satellite communication). They help construct reliable data transmission methods.

Unlock Your Future in Java

Start Your Java Journey for Free Today

Explore Program

Conclusion

From the above article, we conclude that prime numbers can appear just as a maths topic, but they are very useful in real applications too. There are many methods to check whether a number is prime or not, like, using simple loops, checking only up to n/2 or √n. These programs help us understand how logic works in coding. Prime numbers also play an important role in things like online security, secret codes, and even music! So, learning about them is not only helpful for exams and interviews but also for real-life problem-solving.

If you want to learn more about this topic, you can refer to our Java course.

Prime Number in Java – FAQs