Given an integer N. The task is to find Mobius function of all numbers from 1 to N.
Examples:
Input: N = 5
Output: 1 -1 -1 0 -1
Input: N = 10
Output: 1 -1 -1 0 -1 1 -1 0 0 1
Approach: The idea is to first find the least prime factor of all the numbers from 1 to N using Sieve of Eratosthenes then using these least prime factors the Mobius function can be calculated for all the numbers, depending on a number contains an odd number of distinct primes or even number of distinct primes.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;#define N 100005int lpf[N];// Function to calculate least// prime factor of each numbervoid least_prime_factor(){ for (int i = 2; i < N; i++) // If it is a prime number if (!lpf[i]) for (int j = i; j < N; j += i) // For all multiples which are not // visited yet. if (!lpf[j]) lpf[j] = i;}// Function to find the value of Mobius function// for all the numbers from 1 to nvoid Mobius(int n){ // To store the values of Mobius function int mobius[N]; for (int i = 1; i < N; i++) { // If number is one if (i == 1) mobius[i] = 1; else { // If number has a squared prime factor if (lpf[i / lpf[i]] == lpf[i]) mobius[i] = 0; // Multiply -1 with the previous number else mobius[i] = -1 * mobius[i / lpf[i]]; } } for (int i = 1; i <= n; i++) cout << mobius[i] << " ";}// Driver codeint main(){ int n = 5; // Function to find least prime factor least_prime_factor(); // Function to find mobius function Mobius(n);} |
Java
// Java implementation of the approachimport java.util.*;class GFG {static int N = 100005;static int []lpf = new int[N];// Function to calculate least// prime factor of each numberstatic void least_prime_factor(){ for (int i = 2; i < N; i++) // If it is a prime number if (lpf[i] % 2 != 1) for (int j = i; j < N; j += i) // For all multiples which are not // visited yet. if (lpf[j] % 2 != 0) lpf[j] = i;}// Function to find the value of Mobius function// for all the numbers from 1 to nstatic void Mobius(int n){ // To store the values of Mobius function int []mobius = new int[N]; for (int i = 1; i < N; i++) { // If number is one if (i == 1) mobius[i] = 1; else { // If number has a squared prime factor if (lpf[i / lpf[i]] == lpf[i]) mobius[i] = 0; // Multiply -1 with the previous number else mobius[i] = -1 * mobius[i / lpf[i]]; } } for (int i = 1; i <= n; i++) System.out.print(mobius[i] + " ");}// Driver codepublic static void main(String[] args){ int n = 5; Arrays.fill(lpf, -1); // Function to find least prime factor least_prime_factor(); // Function to find mobius function Mobius(n);}} // This code is contributed by PrinciRaj1992 |
Python3
# Python3 implementation of the approach N = 100005lpf = [0] * N; # Function to calculate least # prime factor of each number def least_prime_factor() : for i in range(2, N) : # If it is a prime number if (not lpf[i]) : for j in range(i, N, i) : # For all multiples which are not # visited yet. if (not lpf[j]) : lpf[j] = i; # Function to find the value of Mobius function # for all the numbers from 1 to n def Mobius(n) : # To store the values of Mobius function mobius = [0] * N; for i in range(1, N) : # If number is one if (i == 1) : mobius[i] = 1; else : # If number has a squared prime factor if (lpf[i // lpf[i]] == lpf[i]) : mobius[i] = 0; # Multiply -1 with the previous number else : mobius[i] = -1 * mobius[i // lpf[i]]; for i in range(1, n + 1) : print(mobius[i], end = " "); # Driver code if __name__ == "__main__" : n = 5; # Function to find least prime factor least_prime_factor(); # Function to find mobius function Mobius(n); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the approachusing System;class GFG{static int N = 100005;static int []lpf = new int[N];// Function to calculate least// prime factor of each numberstatic void least_prime_factor(){ for (int i = 2; i < N; i++) // If it is a prime number if (lpf[i] % 2 != 1) for (int j = i; j < N; j += i) // For all multiples which // are not visited yet. if (lpf[j] % 2 != 0) lpf[j] = i;}// Function to find the value of // Mobius function for all the numbers// from 1 to nstatic void Mobius(int n){ // To store the values of // Mobius function int []mobius = new int[N]; for (int i = 1; i < N; i++) { // If number is one if (i == 1) mobius[i] = 1; else { // If number has a squared prime factor if (lpf[i / lpf[i]] == lpf[i]) mobius[i] = 0; // Multiply -1 with the // previous number else mobius[i] = -1 * mobius[i / lpf[i]]; } } for (int i = 1; i <= n; i++) Console.Write(mobius[i] + " ");}// Driver codestatic public void Main (){ int n = 5; Array.Fill(lpf, -1); // Function to find least prime factor least_prime_factor(); // Function to find mobius function Mobius(n);}} // This code is contributed by ajit. |
Javascript
<script>// Javascript implementation of the approachconst N = 100005;let lpf = new Array(N);// Function to calculate least// prime factor of each numberfunction least_prime_factor(){ for (let i = 2; i < N; i++) // If it is a prime number if (!lpf[i]) for (let j = i; j < N; j += i) // For all multiples which are not // visited yet. if (!lpf[j]) lpf[j] = i;}// Function to find the value of Mobius function// for all the numbers from 1 to nfunction Mobius(n){ // To store the values of Mobius function let mobius = new Array(N); for (let i = 1; i < N; i++) { // If number is one if (i == 1) mobius[i] = 1; else { // If number has a squared prime factor if (lpf[parseInt(i / lpf[i])] == lpf[i]) mobius[i] = 0; // Multiply -1 with the previous number else mobius[i] = -1 * mobius[parseInt(i / lpf[i])]; } } for (let i = 1; i <= n; i++) document.write(mobius[i] + " ");}// Driver code let n = 5; // Function to find least prime factor least_prime_factor(); // Function to find mobius function Mobius(n);</script> |
1 -1 -1 0 -1
Time Complexity: O(N2)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

… [Trackback]
[…] There you can find 40849 more Information on that Topic: geeksforgeeks.org/program-for-mobius-function-set-2/ […]
… [Trackback]
[…] Find More on that Topic: geeksforgeeks.org/program-for-mobius-function-set-2/ […]
… [Trackback]
[…] Information to that Topic: geeksforgeeks.org/program-for-mobius-function-set-2/ […]
… [Trackback]
[…] Find More here to that Topic: geeksforgeeks.org/program-for-mobius-function-set-2/ […]