Program for Mobius Function | Set 2 | Python3 implementation of the approach ; Function to calculate least prime factor of each number ; If it is a prime number ; For all multiples which are not visited yet . ; Function to find the value of Mobius function for all the numbers from 1 to n ; To store the values of Mobius function ; If number is one ; If number has a squared prime factor ; Multiply - 1 with the previous number ; Driver code ; Function to find least prime factor ; Function to find mobius function
N = 100005 NEW_LINE lpf = [ 0 ] * N ; NEW_LINE def least_prime_factor ( ) : NEW_LINE INDENT for i in range ( 2 , N ) : NEW_LINE INDENT if ( not lpf [ i ] ) : NEW_LINE INDENT for j in range ( i , N , i ) : NEW_LINE INDENT if ( not lpf [ j ] ) : NEW_LINE INDENT lpf [ j ] = i ; NEW_LINE DEDENT DEDENT DEDENT DEDENT DEDENT def Mobius ( n ) : NEW_LINE INDENT mobius = [ 0 ] * N ; NEW_LINE for i in range ( 1 , N ) : NEW_LINE INDENT if ( i == 1 ) : NEW_LINE INDENT mobius [ i ] = 1 ; NEW_LINE DEDENT else : NEW_LINE INDENT if ( lpf [ i // lpf [ i ] ] == lpf [ i ] ) : NEW_LINE INDENT mobius [ i ] = 0 ; NEW_LINE DEDENT else : NEW_LINE INDENT mobius [ i ] = - 1 * mobius [ i // lpf [ i ] ] ; NEW_LINE DEDENT DEDENT DEDENT for i in range ( 1 , n + 1 ) : NEW_LINE INDENT print ( mobius [ i ] , end = " ▁ " ) ; NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 5 ; NEW_LINE least_prime_factor ( ) ; NEW_LINE Mobius ( n ) ; NEW_LINE DEDENT