Minimum number of Square Free Divisors | Python 3 Program to find the minimum number of square free divisors ; Initializing MAX with SQRT ( 10 ^ 6 ) ; Create a boolean array " prime [ 0 . . n ] " and initialize all entries it as true . A value in prime [ i ] will finally be false if i is Not a prime , else true . ; If prime [ p ] is not changed , then it is a prime ; Update all multiples of p ; Print all prime numbers ; This function returns the minimum number of Square Free divisors ; Precomputing Prime Factors ; holds max of max power of all prime factors ; holds the max power of current prime factor ; If number itself is prime , it will be included as answer and thus minimum required answer is 1 ; Driver Code
from math import sqrt NEW_LINE MAX = 1005 NEW_LINE def SieveOfEratosthenes ( primes ) : NEW_LINE INDENT prime = [ True for i in range ( MAX ) ] NEW_LINE for p in range ( 2 , int ( sqrt ( MAX ) ) + 1 , 1 ) : NEW_LINE INDENT if ( prime [ p ] == True ) : NEW_LINE INDENT for i in range ( p * 2 , MAX , p ) : NEW_LINE INDENT prime [ i ] = False NEW_LINE DEDENT DEDENT DEDENT for p in range ( 2 , MAX , 1 ) : NEW_LINE INDENT if ( prime [ p ] ) : NEW_LINE INDENT primes . append ( p ) NEW_LINE DEDENT DEDENT return primes NEW_LINE DEDENT def minimumSquareFreeDivisors ( N ) : NEW_LINE INDENT prime = [ ] NEW_LINE primes = [ ] NEW_LINE primes = SieveOfEratosthenes ( prime ) NEW_LINE max_count = 0 NEW_LINE i = 0 NEW_LINE while ( len ( primes ) and primes [ i ] * primes [ i ] <= N ) : NEW_LINE INDENT if ( N % primes [ i ] == 0 ) : NEW_LINE INDENT tmp = 0 NEW_LINE while ( N % primes [ i ] == 0 ) : NEW_LINE INDENT tmp += 1 NEW_LINE N /= primes [ i ] NEW_LINE DEDENT max_count = max ( max_count , tmp ) NEW_LINE DEDENT i += 1 NEW_LINE DEDENT if ( max_count == 0 ) : NEW_LINE INDENT max_count = 1 NEW_LINE DEDENT return max_count NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 24 NEW_LINE print ( " Minimum ▁ Number ▁ of ▁ Square ▁ Free ▁ Divisors ▁ is " , minimumSquareFreeDivisors ( N ) ) NEW_LINE N = 6 NEW_LINE print ( " Minimum ▁ Number ▁ of ▁ Square ▁ Free ▁ Divisors ▁ is " , minimumSquareFreeDivisors ( N ) ) NEW_LINE DEDENT