Program for Mobius Function | Set 2 | Java 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
import java . util . * ; class GFG { static int N = 100005 ; static int [ ] lpf = new int [ N ] ; static void least_prime_factor ( ) { for ( int i = 2 ; i < N ; i ++ ) if ( lpf [ i ] % 2 != 1 ) for ( int j = i ; j < N ; j += i ) if ( lpf [ j ] % 2 != 0 ) lpf [ j ] = i ; } static void Mobius ( int n ) { int [ ] mobius = new int [ N ] ; for ( int i = 1 ; i < N ; i ++ ) { if ( i == 1 ) mobius [ i ] = 1 ; else { if ( lpf [ i / lpf [ i ] ] == lpf [ i ] ) mobius [ i ] = 0 ; else mobius [ i ] = - 1 * mobius [ i / lpf [ i ] ] ; } } for ( int i = 1 ; i <= n ; i ++ ) System . out . print ( mobius [ i ] + " ▁ " ) ; } public static void main ( String [ ] args ) { int n = 5 ; Arrays . fill ( lpf , - 1 ) ; least_prime_factor ( ) ; Mobius ( n ) ; } }