Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What are Prime Numbers?
3.
Program to Check Prime Number using a for loop
3.1.
Java
3.2.
Input
3.3.
Output
3.4.
Explanation
4.
Program to Check Prime Number using a while loop
4.1.
Java
4.2.
Input
4.3.
Output
4.4.
Explanation
5.
Naive Approach for Writing Prime Number Program in Java
5.1.
Java
6.
Optimised Approach to Write Prime Number Program in Java
6.1.
Java
7.
Frequently Asked Questions
7.1.
How do you write a prime number program in Java?
7.2.
What is the method to find a prime number in Java?
7.3.
What are the first 10 prime numbers print? 
7.4.
What is the logic of a prime number?
8.
Conclusion
Last Updated: Mar 27, 2024
Easy

Prime Number Program in Java

Author Nikhil Joshi
0 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction

Hi Ninjas, Welcome Back!

Do you know that the Prime number has many applications in computer science? They are very useful in the Cyber security world. Their mathematical property is useful in encryption decryption technology. They are used to generate pseudo-random numbers as well as for the creation of hash tables.

prime number program in java

In this article, we will learn about prime numbers. We will learn how to write a Prime number program in Java and its explanation.

What are Prime Numbers?

A definition that we all had studied in our school days says that Prime numbers are the numbers that are either divisible by one or by themselves. In other words, there should not be any number except one, and the number itself, which can divide the number, then the number is said to be a prime number. 

Following are some facts about Prime Numbers:

  • Two (2) is the only even prime number. All the other even numbers have two (2) as one of the factors.
     
  • No prime number greater than five ends in a 5. Any number greater than five (5) that ends in a five can be divided by five (5).
     
  • Zero and one are not considered prime numbers.
     
  • Except for 0 and 1, a number is either a prime or composite number. A composite number is any number greater than one that is not prime.

 

Let’s see the different algorithms for writing Prime Number Programs in Java.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Program to Check Prime Number using a for loop

Java program to check if a given number is prime using a for loop:

  • Java

Java

import java.util.Scanner;

class Prime_Number {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();

if(isPrime(num)) {
System.out.println(num + " is a prime number");
} else {
System.out.println(num + " is not a prime number");
}
}

public static boolean isPrime(int num) {
if (num < 2) {
return false;
}
for (int i = 2; i <= Math.sqrt(num); i++) {
if (num % i == 0) {
return false;
}
}
return true;
}
}

Input

13

Output

13 is a prime number

Explanation

This Java program checks if a given number is prime. It prompts the user for input, then utilizes a `for` loop to iterate from 2 up to the square root of the number. Within each iteration, it checks if the number is divisible by the current value of `i`. If a divisor is found, it concludes the number is not prime. If no divisors are found, it's a prime number. 

Program to Check Prime Number using a while loop

Java program to check if a given number is prime using a while loop:

  • Java

Java

import java.util.Scanner;

class PrimeCheck {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int num = scanner.nextInt();

if(isPrime(num)) {
System.out.println(num + " is a prime number");
} else {
System.out.println(num + " is not a prime number");
}

}

public static boolean isPrime(int num) {
if (num < 2) {
return false;
}
int i = 2;
while (i <= Math.sqrt(num)) {
if (num % i == 0) {
return false;
}
i++;
}
return true;
}
}

Input

17

Output

17 is a prime number

Explanation

This Java program checks if a given number is prime using a `while` loop. It starts by prompting the user for input. The `isPrime` method iterates from 2 up to the square root of the number using a `while` loop, checking for divisibility in each iteration. If a divisor is found, it concludes the number is not prime. If no divisors are found, it deems the number as prime. 

Naive Approach for Writing Prime Number Program in Java

As per the definition, A number n is a prime number if there is no number b/w one and n that can divide n. 

We are going to use this simple fact to write our program.

Code in Java

  • Java

Java

public class PrimeNumber {
   // function to check if a number is prime
   private static boolean isPrime(int number){
       // variable to store if the number is prime
       boolean isNumberPrime = true;
      
       /*
          loop in the range [2,number-1] to check
          if there is any integer that can divide
          the number.
       */
       for(int i=2; i<number; i++){
           if( (number % i) == 0 ) {
               isNumberPrime = false;
               break;
           }
       }
       return isNumberPrime;
   }

   public static void main(String[] args) {
      
       // Defining two number 7 and 8
      
       int number1 = 7;
       int number2 = 8;


       // checking if they are prime or not
       boolean result1 = isPrime(number1);
       boolean result2 = isPrime(number2);


       // Printing the result
       System.out.println(number1+" is "+((result1)? "a Prime number":" not a Prime number"));
       System.out.println(number2+" is "+((result2)? "a Prime number":" not a Prime number"));
   }
}


Output

Output

Explanation

We have made isPrime function to determine if a number is prime. This function takes a number (an integer) as its parameter. Then we loop on the range two to number-1 to check if any number divides the “number”. If any integer exists between two and number-1 that divides the number, then the “number” is not a prime, and hence we assign isNumberPrime as false.

Time and Space Complexity

  • Looping over the range [2, number-1] will take O(n) operations, and hence the time complexity is O(n).
  • We are not using any extra space except for variables like isNumberPrime; hence, the space complexity is O(1).

Optimised Approach to Write Prime Number Program in Java

Let’s see the factors of a number to find some pattern:

36 = (1,2,3,4),(6),(36,18,12,9).


We have kept factors of 36 in three groups. If we multiply a member of the first group by the respective member of the second group, we will get 36, i.e. 

1*36 = 36, 2*18 = 36, 3*12 = 36, 4*9 = 36.


So, when we check that if 36 is divisible by the member of the first group, then we are not required to check the same by the second group. This led to the observation that we only need to check factors until sqrt(n) to determine whether it is prime.

Let’s verify the fact with another number, 12.

12 = (1,2,3),(12,6,4).


We have only two groups in this case because 12 is not a perfect square. Here also, multiplying the respective members of the first and second groups will result in 12. So, we only need to check factors until sqrt(12) ~ 3 to determine whether it is prime.

Code in Java

  • Java

Java

public class PrimeNumber {
   // function to check if a number is prime
   private static boolean isPrime(int number){
       // variable to store if the number is prime
       boolean isNumberPrime = true;


       /*
          loop in the range [2,sqrt(n)] to check
          if there is any odd integer that can divide
          the number.
       */
       for(int i = 2; i * i <= number; i++ ){
           if( (number % i) == 0 ) {
               isNumberPrime = false;
               break;
           }
       }
       return isNumberPrime;
   }


   public static void main(String[] args) {


       // Defining two number 49456 and 123677


       int number1 = 49456;
       int number2 = 123677;


       // checking if they are prime or not
       boolean result1 = isPrime(number1);
       boolean result2 = isPrime(number2);


       // Printing the result
       System.out.println(number1+" is "+((result1)? "a Prime number": "not a Prime number"));
       System.out.println(number2+" is "+((result2)? "a Prime number": "not a Prime number"));
   }
}


Output

Output

Explanation

We have made isPrime function to determine if a number is a prime. This function takes a number (an integer) as its parameter. Then we loop on the range two to sqrt(n) to check if any integer exists that divides the number, then the “number” is not a prime, and hence we assign isNumberPrime as false. We are using the expression i * i <= number to stop the execution of the loop when the integer lies outside the mentioned range.

Time and Space Complexity

  • Looping over the range [2, sqrt(n)] will take O(sqrt(n)) operations, and hence the time complexity is O(sqrt(n)).
  • We are not using any extra space except for variables like isNumberPrime; hence, the space complexity is O(1).

Frequently Asked Questions

How do you write a prime number program in Java?

In Java, write a program that iterates through numbers, checking for factors up to their square root. If a number has no factors other than 1 and itself, it's prime.

What is the method to find a prime number in Java?

The method involves iterating from 2 to the square root of the number and checking for divisibility. If the number is only divisible by 1 and itself, it's prime.

What are the first 10 prime numbers print? 

The first ten prime numbers are: 2, 3, 5, 7, 11, 13, 17, 19, 23, and 29. These are natural numbers greater than 1 that have no divisors other than 1 and themselves.

What is the logic of a prime number?

A prime number is one that's only divisible by 1 and itself. To determine if a number is prime, iterate from 2 to its square root. If it's divisible by any number in this range, it's not prime; otherwise, it is.

Conclusion

In conclusion, we can say that prime number program in java are very important in computer science. They have diverse applications. We can find if a number is prime using various approaches. In this article, we improved approach by approach, and, finally, the most optimised algorithm has taken O(sqrt(n)) operations to determine if a number is prime.

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc.

Happy Learning!

Previous article
Java Hello World Program
Next article
Menu Driven Program in Java
Live masterclass