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 in N 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 1:
INPUT: 78
OUTPUT:
78 = 2 × 3 × 13
NUMBER OF DISTINCT PRIME FACTORS = 3
M(78) = -1
Sample 2:
INPUT: 34
OUTPUT:
34 = 2 × 17
NUMBER OF DISTINCT PRIME FACTORS = 2
M(34) = 1
Sample 3:
INPUT: 12
OUTPUT:
12 = 2 × 2 × 3
DUPLICATE PRIME FACTORS
M(12) = 0
Sample 4:
INPUT: 1
OUTPUT:
1 = 1
NO PRIME FACTORS
M(1) = 1
import java.util.Scanner;
class Mobius{
public static void main(String args[]){
Scanner in = new Scanner(System.in);
System.out.print("N = ");
int n = Integer.parseInt(in.nextLine());
int m = mob(n);
System.out.println("M(" + n + ") = " + m);
}
public static int mob(int n){
int pf = 2;
int total = 0;
boolean distinct = true;
if(n == 1){
System.out.println("NO PRIME FACTORS");
return 1;
}
while(n > 1){
int count = 0;
while(n % pf == 0){
n /= pf;
System.out.print(pf);
count++;
total++;
if(count > 1)
distinct = false;
if(n > 1)
System.out.print(" x ");
}
pf++;
}
System.out.println();
if(distinct){
System.out.println("NUMBER OF DISTINCT PRIME FACTORS = " + total);
if(total % 2 == 0)
return 1;
else
return -1;
}
System.out.println("DUPLICATE PRIME FACTORS");
return 0;
}
}