Prime Numbers

Optimized Method

But the above way is not an efficient way to check the prime numbers. As we all know, when we do multiplication, 2*5 will produce the same result as 5*2, which will be 10. So if 10 is the number as input, then it gets divided by 2, which is less than 10/2, i.e., 5. So let's try to implement that through codes.

public class prime {
    public static void main(String[] args) {
        num = 10;
  boolean ans = isPrime(num);
        if(ans)
            System.out.println(num + " is Prime number");
        else
            System.out.println(num + " is not a Prime number");
        scn.close();
    }

    public static boolean isPrime(int n) {
      if(n < 2) return false;
      for(int i=2; i<n/2; i++)
      {
         if(n%i == 0)
              return false;
     }
      return true;
  }
}

Output : 

10 is not a Prime number

As you can see, the only change done is in the function isPrime for loop. The for loop condition only gets changed to find the prime numbers. Now it runs only till n/2 times, thus helping in reducing the running time of the for loop.

We can reduce the running time by changing the program for loop conditions as we go further. It is a much more optimized way to find the prime number. If a number has a factor, then its(factor's) square is smaller than or equal to the number.

public class prime {
    public static void main(String[] args) {
        num = 10;
  boolean ans = isPrime(num);
        if(ans)
            System.out.println(num + " is Prime number");
        else
            System.out.println(num + " is not a Prime number");
        scn.close();
    }

   public static boolean isPrime(int n) {
  if(n < 2) return false;
        for(int i=2; i*i<=n; i++)
        {
            if(n%i == 0)
                return false;
        }
        return true;
}
}

You can also try this code with Online Java Compiler

Run Code

Output:

10 is not a Prime number

You can also try this code with Online Java Compiler

Run Code

Instead of using for loop, we can use while loop to achieve the same results. The only change will be the way we write the condition.

public class prime {
    public static void main(String[] args) {
        num = 5;
  boolean ans = isPrime(num);
        if(ans)
            System.out.println(num + " is Prime number");
        else
            System.out.println(num + " is not a Prime number");
        scn.close();
    }

    public static boolean isPrime(int n) {
       if(n < 2) return false;
        int i=2;
        while(i*i<=n)
        {
            if(n%i == 0)
                return false;
            i++;
        }
        return true;
    }
}

You can also try this code with Online Java Compiler

Run Code

Output:

5 is Prime number

You can also try this code with Online Java Compiler

Run Code

Time complexity : O(√n)

Space complexity : O(1)

Practice it on online java compiler for better understanding.

Recursion method

All the above-discussed ways of finding the prime number are iterative. But we can also program recursively. It is the alternative to the iterative method. Multiple conditions will be there in the base case. If any condition is fulfilled, it will return the answer to the main function from where the isPrime() function is called.

public class prime {
    public static void main(String[] args) {
        num = 10;
  boolean ans = isPrime(num);
        if(ans)
            System.out.println(num + " is Prime number");
        else
            System.out.println(num + " is not a Prime number");
        scn.close();
    }

public static boolean isPrime(int num, int i) {
        if (num <= 2)
            return (num == 2) ? true : false; // 0 & 1 are not prime
        else if (num % i == 0)
            return false;
        else if (i * i > num)
            return true;
        else
            return isPrime(num, i + 1);
}
}

You can also try this code with Online Java Compiler

Run Code

Output:

5 is Prime number

You can also try this code with Online Java Compiler

Run Code

Time complexity : O(√n)

Space complexity : O(n)

Also check out Addition of Two Numbers in Java here.

Also see, Duck Number in Java

FAQs

1. What is a prime number?
   Numbers that are divisible by one and number itself are called prime numbers.
    
2. Can we make a program to find prime numbers without using loops?
   Instead of using an iterative method, you can write the program using a recursive process.
    
3. Is it compulsory to have a return type in the isPrime function?
   No, it is not compulsory. You can directly print the answer in the isPrime() function before returning it to the main() function.
    
4. Are zero and one considered prime numbers?
   No, they are not prime numbers.

Key Takeaways

In this article, we have extensively discussed the prime numbers and their implementation in java.

Prime numbers are those numbers that have only two factors, i.e., one and the number itself. This blog has discussed different methods from brute force to the most optimized way to find whether a number is a prime number or not. 

Recommended Problem - K Closest Points To Origin

We hope that this blog has helped you enhance your knowledge regarding how to write a program to check whether a given number is prime numbers and if you would like to learn more, check out our articles on prime numbers in C++. Do upvote our blog to help other ninjas grow. Happy Coding!