Product of Primes Geeks For Geeks
Problem Link:
https://practice.geeksforgeeks.org/problems/product-of-primes5328/1#
(It is also the problem of the day for 24-04-2022)
Solution:
class Solution{
public static boolean checkPrime(int n){
if(n==1){
return false;
}
else if(n==2 || n==3){
return true;
}
else if(n%2==0 || n%3==0){
return false;
}
else{
for(int i=5;i<Math.sqrt(n)+1;i+=6){
if(n%i==0 || n%(i+2)==0){
return false;
}
}
return true;
}
}
static long primeProduct(long l, long r){
long p=01;
for(int i=(int)l;i<((int)r+1);i++){
if(checkPrime(i)==true){
p=(p*i)%1000000007;
}
}
return p;
}
}
Time Complexity: O((r-l)*(Math.sqrt(number)))[GFG Time:0.21/2.68] [Here number varies from l to r and taking it in worst case it will be r so worst-case complexity will be : O((r-l)*(Math.sqrt(r))]
Space Complexity: O(1)
Auxiliary Space: O(1)[Only constants are used]
Total Test Cases:58
Approach Used:
Here we used the approach of
1. check whether the number is prime or not
2. multiply the number if it is prime.
For checking of prime we will pass each element to the checkPrime function and check its nature:
In the checkPrime 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.
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.)
long p=1
And if it is prime then multply it with variable p and every time when you multiply take modulus with 1000000007 so as to avoid long overflow error.
"Thanks For Reading.😇"
"Share Further To Increase Knowledge Treasure.😊"
Comments
Post a Comment