Program opened below. You can scroll through the algorithm, Java code and output.
Program 23
Mobius Function
Question
Input a natural number n and calculate μ(n): 1 for n=1, 0 if a squared prime factor divides n, otherwise (−1) raised to the number of distinct prime factors.
Algorithm
Step 1: Start and input natural number n.
Step 2: Reject numbers less than one.
Step 3: Copy n to a temporary factorization variable.
Step 4: Initialize the distinct-prime-factor count to zero.
Step 5: Initialize the result to one.
Step 6: Examine possible prime divisors starting from two.
Step 7: When a divisor divides the number, count a new prime factor.
Step 8: Divide the remaining number once by that divisor.
Step 9: Check whether the same divisor still divides it.
Step 10: If repeated, set the result to zero because a squared prime factor is present.
Step 11: Otherwise remove any remaining occurrence if applicable.
Step 12: Continue testing possible factors.
Step 13: If the remaining factor exceeds one, count it as a prime factor.
Step 14: For square-free numbers, return negative one for an odd count and positive one for an even count.
Step 15: Display the calculated Mobius function and stop.
Java program
Javaimport java.util.*;
class Mobius {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
if (n < 1) {
System.out.println("Invalid number");
return;
}
int temp = n;
int factors = 0;
int answer = 1;
for (int p = 2; p <= temp / p; p++) {
if (temp % p == 0) {
factors++;
temp /= p;
if (temp % p == 0) {
answer = 0;
break;
}
}
while (temp % p == 0) {
temp /= p;
}
}
if (answer != 0) {
if (temp > 1) {
factors++;
}
if (factors % 2 == 1) {
answer = -1;
}
}
System.out.println("Mobius = " + answer);
}
}Sample output
Input: 46
Output: Mobius = 1