‹ Back to the paper
Write the program described below.
A MOBIUS function M(N) returns the value -1 or 0 or 1 for a natural number (N) by the following…
A MOBIUS function $M(N)$ returns the value $-1$ or $0$ or $1$ for a natural number ($N$) by the following conditions are defined:
When,
$M(N) = 1$ if $N = 1$.
$M(N) = 0$ if any prime factor of $N$ is contained more than once.
$M(N) = (-1)^P$ if $N$ is the product of ‘P’ distinct prime factors.
Write a program to accept a positive natural number ($N$) and display the MOBIUS result with proper message.
Design your program which will enable the output in the format given below:
Sample input/output
Sample 1
INPUT: 78
OUTPUT: 78 = 2 x 3 x 13
NUMBER OF DISTINCT PRIME FACTORS = 3
M(78) = -1
Sample 2
INPUT: 34
OUTPUT: 34 = 2 x 17
NUMBER OF DISTINCT PRIME FACTORS = 2
M(34) = 1
Sample 3
INPUT: 12
OUTPUT: 12 = 2 x 2 x 3
DUPLICATE PRIME FACTORS
M(12) = 0
Sample 4
INPUT: 1
OUTPUT: 1 = 1
NO PRIME FACTORS
M(1) = 1Answer
Answer
import java.util.Scanner;
public class Mobius
{
public static void main(String args[])
{
Scanner sc = new Scanner(System.in);
System.out.print("INPUT: ");
int n = sc.nextInt();
if (n < 1)
{
System.out.println("INVALID INPUT");
return;
}
int t = n;
String expr = "";
int distinct = 0;
boolean dup = false;
int prev = 0;
for (int i = 2; i <= t; i++)
{
while (t % i == 0)
{
if (expr.equals(""))
expr = "" + i;
else
expr = expr + " x " + i;
if (i == prev)
dup = true;
else
distinct++;
prev = i;
t = t / i;
}
}
System.out.println();
if (n == 1)
{
System.out.println("1 = 1");
System.out.println("NO PRIME FACTORS");
System.out.println("M(1) = 1");
}
else
{
System.out.println(n + " = " + expr);
int m;
if (dup)
{
System.out.println("DUPLICATE PRIME FACTORS");
m = 0;
}
else
{
System.out.println("NUMBER OF DISTINCT PRIME FACTORS = " + distinct);
m = (distinct % 2 == 0) ? 1 : -1;
}
System.out.println("M(" + n + ") = " + m);
}
}
}