Practical Numbers | Python3 program to check if a number is Practical or not . ; Returns true if there is a subset of set [ ] with sun equal to given sum ; The value of subset [ i ] [ j ] will be true if there is a subset of set [ 0. . j - 1 ] with sum equal to i ; If sum is 0 , then answer is true ; If sum is not 0 and set is empty , then answer is false ; Fill the subset table in bottom up manner ; Function to store divisors of N in a vector ; Find all divisors which divides 'num ; If ' i ' is divisor of 'n ; If both divisors are same then store it once else store both divisors ; Returns true if num is Practical ; Vector to store all divisors of N ; To check all numbers from 1 to < N ; Driver code
import math NEW_LINE def isSubsetSum ( Set , n , Sum ) : NEW_LINE INDENT subset = [ [ False for i in range ( Sum + 1 ) ] for j in range ( n + 1 ) ] NEW_LINE for i in range ( n + 1 ) : NEW_LINE INDENT subset [ i ] [ 0 ] = True NEW_LINE DEDENT for i in range ( 1 , Sum + 1 ) : NEW_LINE INDENT subset [ 0 ] [ i ] = False NEW_LINE DEDENT for i in range ( 1 , n + 1 ) : NEW_LINE INDENT for j in range ( 1 , Sum + 1 ) : NEW_LINE INDENT if ( j < Set [ i - 1 ] ) : NEW_LINE INDENT subset [ i ] [ j ] = subset [ i - 1 ] [ j ] NEW_LINE DEDENT if ( j >= Set [ i - 1 ] ) : NEW_LINE INDENT subset [ i ] [ j ] = ( subset [ i - 1 ] [ j ] or subset [ i - 1 ] [ j - Set [ i - 1 ] ] ) NEW_LINE DEDENT DEDENT DEDENT return subset [ n ] [ Sum ] NEW_LINE DEDENT def storeDivisors ( n , div ) : NEW_LINE ' NEW_LINE INDENT for i in range ( 1 , int ( math . sqrt ( n ) ) + 1 ) : NEW_LINE DEDENT ' NEW_LINE INDENT if ( n % i == 0 ) : NEW_LINE INDENT if ( i == int ( n / i ) ) : NEW_LINE INDENT div . append ( i ) NEW_LINE DEDENT else : NEW_LINE INDENT div . append ( i ) NEW_LINE div . append ( int ( n / i ) ) NEW_LINE DEDENT DEDENT DEDENT def isPractical ( N ) : NEW_LINE INDENT div = [ ] NEW_LINE storeDivisors ( N , div ) NEW_LINE for i in range ( 1 , N ) : NEW_LINE INDENT if ( not isSubsetSum ( div , len ( div ) , i ) ) : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT return True NEW_LINE DEDENT N = 18 NEW_LINE if ( isPractical ( N ) ) : NEW_LINE INDENT print ( " Yes " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT