If m and n are positive integer and n is a divisor or factor of m then there exists a non zero integer p such that :
n * p = m where (n , p , m > 0) and n | m (Usual notation to show n is divisor of m)
Case : We need to find a if a number is multiplier of two prime numbers so we need to find n and p such that n * p = m
E.g ,
Input =35 then output = true [ 35 = 7 * 5 (both are prime numbers)]
Input =21 then output = true [21 = 7 * 3 ]
Input =20 then output = false [20 = 2 * 10 or 4 *5 not prime numbers]
Code snippet :
n * p = m where (n , p , m > 0) and n | m (Usual notation to show n is divisor of m)
Case : We need to find a if a number is multiplier of two prime numbers so we need to find n and p such that n * p = m
E.g ,
Input =35 then output = true [ 35 = 7 * 5 (both are prime numbers)]
Input =21 then output = true [21 = 7 * 3 ]
Input =20 then output = false [20 = 2 * 10 or 4 *5 not prime numbers]
Code snippet :
public static boolean checkMultiplierOfPrime(int n){
if( n< 6){
return false; ///as least number satifying the condition is 6 = 2 * 3
}
int k = (int) Math.sqrt(n); /////important catch here to find the square root
for (int i = k; i >= 2; i--) {
if(n % i == 0){
int j = n/i;
if(isPrimeNumber(i) && isPrimeNumber(j)){
return true;
}
}
}
return false;
}
public static boolean isPrimeNumber(int number){
if(number<=1){
return false;
}
for(int i=2; i<=number/2; i++){
if(number % i == 0){
return false;
}
}
return true;
}
Time Complexity : O(n) for a number of n , iteration would from 2 to n/2 , hence complexity would be O(n/2) means O(n)
Enjoy the coding !!!!!!
No comments:
Post a Comment