Prime Numbers

#beginners #java #programming

To find prime numbers in a fast and efficient way in O(sqrt(n)) time complexity.

To check prime numbers efficiently any number is a prime number if it is not divisible by any number less than or equal to the square root of the given number.

First we take an input n to check whether it is prime or not.
then the number is checked whether it is a valid number or not as numbers less than or equal to 1 are not prime in which case our function prime return -1 .

Then divisibility by 2 or 3 is checked ,if it is divisible by 2 or 3 then 0 is returned.

Then we check for all numbers below square root of the given number if it is divisible or not.
To check that more efficiently we iterate the variable i starting from 5 and increment it by 6 and we check it is divisible by i and i+2 if it is then 0 is returned else the given number is a prime number.

This program checks for prime numbers in o(sqrt(n)) time complexity.

import java.util.*;
public class Prime {
    static int prime(int n){
        if(n<=1){
            return -1;
        }
        if(n==2||n==3){
            return 1;
        }
        if(n%2==0||n%3==0){
            return 0;
        }
        for(int i=5;i*i<=n;i=i+6){
            if(n%i==0||n%(i+2)==0){
                return 0;
            }
        }
        return 1;
    }
    public static void main(String args[]) {
        Scanner sc=new Scanner(System.in);
        int n,r ;
        System.out.println("Enter the number to check");
        n=sc.nextInt();
        r=prime(n);
        System.out.println(r);
        if(r==-1){
        System.out.println("Please enter a valid number");
        }
        else if(r==0){
            System.out.println(""+n+" is not a prime number");
        }
        else{
            System.out.println("It is a prime number");
        }
    }
}

Top comments (6)

Unfamous Dyson • Oct 27 '21 • Edited

Thanks for this! This was one of my favourite challenges in that it was the first challenge I completed where the solution came from researching math rather than code. The purpose of the challenge was a little different in that you have to optimize the prime number check for performance, as the tests purposely timed out on big numbers: codewars.com/kata/5262119038c0985a...

Here is the code I wrote after researching the math for finding prime numbers:
github.com/HatHeadNinja/katas/blob...