Java Program to Check Prime Number.

In this article, we are going to discuss different approaches to checking if a number is in Prime or not using Java Programming. Before moving to the code part let us understand what are Prime Numbers.

What is Prime Number?

A prime number is a positive integer greater than 1 that has no positive integer divisors other than 1 and itself. In other words, a prime number can only be divided evenly by 1 and itself.

For example, the first few prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, and so on.

There are multiple ways to check if a number is prime or not in Java.

Check Prime Number using Loop.
Check Prime Number using the square root property.
Check Prime Number using the Sieve of Eratosthenes.

Check Prime Number using Loop.

To check if a number is prime is to use a loop and iterate from 2 to n/2 (where n is the number we want to check) and check if n is divisible by any number in this range. If n is divisible by any number in this range, then it is not prime.

Java Code Implementation:

// Java code to check prime using loop
class CheckPrime {
    public static void main(String[] args) {
        boolean check = isPrime(11);
        if(check){
            System.out.println("Number is Prime!");
        }
        else{
            System.out.println("Number is not Prime!");
        }
    }
    public static boolean isPrime(int n) {
        if (n <= 1) {
           return false;
        }
        for (int i = 2; i <= n/2; i++) {
           if (n % i == 0) {
              return false;
           }
        }
        return true;
    }
}

Output:

Number is Prime!

Time Complexity:

The time complexity of this approach is O(n/2) = O(n), where n is the input number. This is because the loop iterates from 2 to n/2 and checks if n is divisible by any of these numbers.

Space Complexity:

The space complexity of this approach is O(1) because only a constant amount of memory is used to store the loop variable and other variables.

Check Prime Number using the square root property.

This approach is to check if n is divisible by any number in the range 2 to sqrt(n) (where sqrt(n) is the square root of n). This approach is more efficient because it reduces the number of iterations in the loop.

Java Code Implementation:

// Java code to check prime using the square root property
class CheckPrime {
    public static void main(String[] args) {
        boolean check = isPrime(7);
        if(check){
            System.out.println("Number is Prime!");
        }
        else{
            System.out.println("Number is not Prime!");
        }
    }
    //function to check prime
    public static boolean isPrime(int n) {
        if (n <= 1) {
           return false;
        }
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
              return false;
            }
        }
        return true;
    }
}

Output:

Number is Prime!

Time Complexity:

The time complexity of this approach is O(sqrt(n)), where n is the input number. This is because the loop iterates from 2 to sqrt(n) and checks if n is divisible by any of these numbers.

Space Complexity:

The space complexity of this approach is O(1) because only a constant amount of memory is used to store the loop variable and other variables.

Check Prime Number using the Sieve of Eratosthenes.

This is a more advanced approach to finding all the prime numbers up to a certain limit.

This algorithm involves creating a boolean array of size n+1 and setting all the values to true. We then iterate from 2 to sqrt(n) and mark all multiples of each number as false. Finally, we iterate through the boolean array and return all the indexes that are marked as true.

Java Code Implementation:

// Java code to check prime using the Sieve of Eratosthenes
import java.util.Arrays;

class HelloWorld {
    public static void main(String[] args) {
        boolean check = isPrime(7);
        if(check){
            System.out.println("Number is Prime!");
        }
        else{
            System.out.println("Number is not Prime!");
        }
    }
    public static boolean[] sieveOfEratosthenes(int n) {
        boolean[] prime = new boolean[n+1];
        Arrays.fill(prime, true);
        prime[0] = false;
        prime[1] = false;
        for (int i = 2; i <= Math.sqrt(n); i++) {
           if (prime[i]) {
               for (int j = i*i; j <= n; j += i) {
                   prime[j] = false;
               }
           }
        }
        return prime;
    }

    public static boolean isPrime(int n) {
       if (n <= 1) {
           return false;
       }
       boolean[] primes = sieveOfEratosthenes(n);
       return primes[n];
    }
}

Output:

Number is Prime!

Time Complexity:

The time complexity of the Sieve of Eratosthenes algorithm is O(n log log n), where n is the input number. This is because the algorithm involves iterating through all numbers up to n and marking multiples of each prime number as composite.

Space Complexity:

The space complexity of this approach is O(n) because we need to store a boolean array of size n+1 to mark all numbers as prime or composite.

Java Program to Check Prime Number.

What is Prime Number?

Check Prime Number using Loop.

Check Prime Number using the square root property.

Check Prime Number using the Sieve of Eratosthenes.

No comments:

Post a Comment