Write a Java program to check whether a given number is prime or not using recursion

The Java code checks whether a given number is prime or not using a recursive function. Here's how the code works:

The main function reads an integer from the user using the Scanner class and passes it to the checkPrimeNot function along with the value num/2 (which is the largest possible factor of num except for num itself).
The checkPrimeNot function takes two arguments - num and i. The function first checks if num is divisible by i. If num is not divisible by i, then it recursively calls checkPrimeNot function with i decremented by 1.
If num is divisible by i, the function returns 0 which indicates that the number is not prime.
If i is decremented to 1 and num is not found to be divisible by any number less than or equal to num/2, then the function returns 1 which indicates that the number is prime.
Finally, the main function prints "This is a Prime Number" if the checkPrimeNot function returns 1 and "This is a Not Prime Number" otherwise.

The implementation seems correct and efficient, as it uses recursion to check all possible factors of the given number until it finds a factor or reaches the minimum possible factor (1). However, for large inputs, the recursion may cause stack overflow due to excessive function calls. A more optimized version can be implemented by checking the factors of the number only up to its square root.

Source Code

import java.util.*;
public class PrimeNot
{
	public static void main(String[] args)
	{
		Scanner input = new Scanner(System.in);
		System.out.printf("Enter the Number : ");
		int num = input.nextInt();
		int res = checkPrimeNot(num, num / 2);
		if (res == 1)
		{
			System.out.printf("This is a Prime Number");
		}
		else
		{
			System.out.printf("This is a Not Prime Number");
		}
	}
	public static int checkPrimeNot(int num, int i)
	{
		if (i != 1)
		{
			if (num % i != 0)
			{
				return checkPrimeNot(num, i - 1);
			}
			return 0;
		}
		return 1;
	}
}

Output

Enter the Number : 71
This is a Prime Number