Find Prime Numbers In Range Geeks For Geeks

 Problem Link:

https://practice.geeksforgeeks.org/problems/find-prime-numbers-in-a-range4718/1

It is also the problem of the day of 8 February.

Solution:

class Solution {

    public boolean isPrime(int a){

        if(a==1){

            return false;

        }

        if(a==2 || a==3){

            return true;

        }

        else if(a%2==0 || a%3==0){

            return false;

        }

        else{

            boolean flag=true;

            for(int i=5;i<=Math.sqrt(a);i+=6){

                if(a%i==0 || a%(i+2)==0){

                    flag=false;

                    break;

                }

            }

            return flag;

        }

    }

    ArrayList<Integer> primeRange(int m, int n) {

        ArrayList<Integer>aa=new ArrayList<Integer>();

        for(int i=m;i<n+1;i++){

            if(isPrime(i)){

                aa.add(i);

            }

        }

        return aa;

    }

}

TIME COMPLEXITY: O(N*SQRT(N))

SPACE COMPLEXITY: O(1)

AUXILLARY SPACE: O(N)[ArrayList is used as returned output]

TOTAL TEST CASES:1016

APPROACH:

Here we will check for every element that is from range m to n whether it is prime or not prime.

For that, we will pass each element to the isPrime function and check its nature.

In the isPrime function:

1. If the number is 1 it will directly return false.

2. If it is 2 or 3 then it will return true.

3. If the number is divisible by 2 or 3 then it will return false a prime number should be divided by 2 or 3.

4. Else we will apply the loop from i=5 to Math. sqrt(number)

and see whether the number is divisible by i or i+2.

eq for 49 it will not go to 1,2 or 3 cases but it will go in 4 cases.

Checking from 5 to Sqrt(49) ie 7 we will see that 49 is not divisible by i=5 but it is divisible by (i+2) ie 7. Hence it is not prime.

(If we do not check for such condition of (i+2)divisibility then we will get the wrong answer.

If yes then we will return false as it will be not prime else it will return true as the number will be prime.

While if we don't apply this condition then we will get true for 49 as i will be 5 only then i will be 11>7 so the loop will break.)

In the worst case,

the time taken for checking one number is Sqrt(N)

so for N elements, the time will be N*Sqrt(N)

Hence time complexity is O(N*Sqrt(N)).

"Thanks For Reading.😇"

"Share Further To Increase Knowledge Treasure.😊"