Program opened below. You can scroll through the algorithm, Java code and output.
Program 62
Möbius Function
Question
Accept a positive integer N. Factorize it. M(1)=1; if any prime factor is repeated, M(N)=0; otherwise M(N)=(-1)^P, where P is the number of distinct prime factors.
Algorithm
Step 1: Start.
Step 2: Declare the variables and data structures required for the task.
Step 3: Start and input N.
Step 4: If N < 1, display INVALID INPUT and stop.
Step 5: Initialize the counters, flags, accumulators or result structures needed by the solution.
Step 6: Set temp=N, factor=2, count=0 and repeated=false.
Step 7: While factor*factor <= temp, divide temp by factor and count its occurrences.
Step 8: If a factor occurs more than once, set repeated=true.
Step 9: If it occurs at least once, increase count and record the factor.
Step 10: After the loop, if temp > 1, count the remaining prime factor.
Step 11: If N=1, set M(N)=1; else if repeated, set M(N)=0; otherwise use (-1)^count.
Step 12: Display the factorization, distinct factor count and Möbius result.
Step 13: Stop.
Java program
Javaimport java.util.*;
class MobiusFunction {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
if (n < 1) {
System.out.println("INVALID INPUT");
return;
}
int temp = n, count = 0;
boolean repeated = false;
StringBuilder factors = new StringBuilder();
for (int p = 2; p * p <= temp; p++) {
int power = 0;
while (temp % p == 0) {
temp /= p;
power++;
}
if (power > 0) {
count++;
if (factors.length() > 0) {
factors.append(" x ");
}
for (int j = 0; j < power; j++) {
factors.append(p).append(j + 1 < power ? " x " : "");
}
if (power > 1) {
repeated = true;
}
}
}
if (temp > 1) {
count++;
if (factors.length() > 0) {
factors.append(" x ");
}
factors.append(temp);
}
if (n == 1) {
factors.append("1");
}
int result = n == 1 ? 1 : (repeated ? 0 : (count % 2 == 0 ? 1 : -1));
System.out.println(n + " = " + factors);
System.out.println("NUMBER OF DISTINCT PRIME FACTORS = " + count);
if (repeated) {
System.out.println("DUPLICATE PRIME FACTORS");
}
else if (n == 1) {
System.out.println("NO PRIME FACTORS");
}
System.out.println("M(" + n + ") = " + result);
}
}Sample output
Input: 78
Output:
78 = 2 x 3 x 13
NUMBER OF DISTINCT PRIME FACTORS = 3
M(78) = -1