Program for Mobius Function | Python Program to evaluate Mobius def M ( N ) = 1 if N = 1 M ( N ) = 0 if any prime factor of N is contained twice M ( N ) = ( - 1 ) ^ ( no of distinctprime factors ) ; def to check if n is prime or not ; Handling 2 separately ; If 2 ^ 2 also divides N ; Check for all other prime factors ; If i divides n ; If i ^ 2 also divides N ; Driver Code
import math NEW_LINE def isPrime ( n ) : NEW_LINE INDENT if ( n < 2 ) : NEW_LINE INDENT return False NEW_LINE DEDENT for i in range ( 2 , n + 1 ) : NEW_LINE INDENT if ( n % i == 0 ) : NEW_LINE INDENT return False NEW_LINE DEDENT i = i * i NEW_LINE DEDENT return True NEW_LINE DEDENT def mobius ( n ) : NEW_LINE INDENT p = 0 NEW_LINE if ( n % 2 == 0 ) : NEW_LINE INDENT n = int ( n / 2 ) NEW_LINE p = p + 1 NEW_LINE if ( n % 2 == 0 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT DEDENT for i in range ( 3 , int ( math . sqrt ( n ) ) + 1 ) : NEW_LINE INDENT if ( n % i == 0 ) : NEW_LINE INDENT n = int ( n / i ) NEW_LINE p = p + 1 NEW_LINE if ( n % i == 0 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT DEDENT i = i + 2 NEW_LINE DEDENT if ( p % 2 == 0 ) : NEW_LINE INDENT return - 1 NEW_LINE DEDENT else : NEW_LINE INDENT return 1 NEW_LINE DEDENT DEDENT N = 17 NEW_LINE print ( " Mobius defs M ( N ) at N = { } is : { } " . format ( N , mobius ( N ) ) ) ; NEW_LINE print ( " Mobius defs M ( N ) at N = 25 is : { } " . format ( mobius ( 25 ) ) ) ; NEW_LINE print ( " Mobius defs M ( N ) at N = 6 is : { } " . format ( mobius ( 6 ) ) ) ; NEW_LINE