Check if there exists a number with X factors out of which exactly K are prime | Python3 program to check if there exists a number with X factors out of which exactly K are prime ; Function to check if such number exists ; To store the sum of powers of prime factors of X which determines the maximum count of numbers whose product can form X ; Determining the prime factors of X ; To check if the number is prime ; If X is 1 , then we cannot form a number with 1 factor and K prime factor ( as K is atleast 1 ) ; If X itself is prime then it can be represented as a power of only 1 prime factor w0hich is X itself so we return true ; If sum of the powers of prime factors of X is greater than or equal to K , which means X can be represented as a product of K numbers , we return true ; In any other case , we return false as we cannot form a number with X factors and K prime factors ; Driver code
from math import sqrt NEW_LINE def check ( X , K ) : NEW_LINE INDENT prime = 0 NEW_LINE temp = X NEW_LINE sqr = int ( sqrt ( X ) ) NEW_LINE for i in range ( 2 , sqr + 1 , 1 ) : NEW_LINE INDENT while ( temp % i == 0 ) : NEW_LINE INDENT temp = temp // i NEW_LINE prime += 1 NEW_LINE DEDENT DEDENT if ( temp > 2 ) : NEW_LINE INDENT prime += 1 NEW_LINE DEDENT if ( X == 1 ) : NEW_LINE INDENT return False NEW_LINE DEDENT if ( prime == 1 and K == 1 ) : NEW_LINE INDENT return True NEW_LINE DEDENT elif ( prime >= K ) : NEW_LINE INDENT return True NEW_LINE DEDENT else : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT X = 4 NEW_LINE K = 2 NEW_LINE if ( check ( X , K ) ) : NEW_LINE INDENT print ( " Yes " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT DEDENT