Tag: isc

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;
    }
}