Prime Number Program in Java

Any natural number is divisible only by itself, and 1 is called a prime number. 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. In this article, we shall see how to build a prime number program in java that can help us identify whether a number is prime or not.

Prime Number Program Using a For Loop

Observe that there cannot be a divisor of a number n greater than n/2. Hence, we can divide the number n with only those natural numbers that 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.

Code:

Output:-

Explanation: We have a variable count, initialized at zero. We start a for loop with a range of 1 to half of the input number and check for divisibility at every point. If the input number is divisible by any of these, the value of the count is incremented. Once the loop ends, we check if the count is greater than 0; if yes, the number is not prime.

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.

Prime Number Program Using a While Loop

Output:

Explanation: Here, we have replaced the for loop with while; the rest of everything is the same as the for loop. Initially, i is 1. The value is incremented until half of the number is reached, and divisibility is checked. If the number is completely divisible at any point, it is not prime.

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.

Prime Number Program Using Method in Java

In this program, the same logic will be used as earlier. The only difference is, logic will be put in a different method which shall be called from the main method.

Output:-

Explanation: In the above code, we're checking if 11 is prime or not, which is being passed as an argument to a boolean static method isPrime(int). Inside this method, we start a for loop from 2 to half the number and check for divisibility. If the input number is completely divisible by any of these, false is returned, and hence the number is not prime.

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.

Prime Number Program Using a Flag Variable

In this section, we shall introduce a boolean flag variable whose value will toggle based on whether a number is prime or not. As the input number becomes completely divisible, the value of the flag variable will toggle, and the loop will break. Let's see how to achieve this.

Output:-

Explanation: The boolean variable flag is initially declared true in the method isPrime(int). We enter the for loop and check for divisibility. If, at any point, the input number is completely divisible, the flag toggles to false, and the loop breaks. The value of the flag is returned.

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

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

Program to Display the Prime Numbers from 1 to 100

We can find all the prime numbers in a given range here. Now, we have to print all the prime numbers between 1 - 100. The logic for checking if a number is prime or not shall remain the same, i.e. divisibility check.

Output:-

Time Complexity: O($n^2$), since for every number we're running an O(n) check, thus for n numbers, it will result in order of O(n * n).

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

Find Prime Numbers between Two Numbers

In this approach, we take two integers as range and then check whether the ith integer is prime or not.

Input:-

Output:-

The output justifies the logic explained above.

Time Complexity: O($n^2$), since for every number we're running an O(n) check, thus for n numbers, it will result in order of O(n * n).

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

Find Prime Number Using Recursion

Output:-

Explanation: In the above code, we have converted the for or while loop iteration in recursion where in each call, we check for i and then if we do not find a result, then move to i+1 until i*i is less than n.