Verify Whether or not a Quantity is an Anti Prime Quantity(Extremely Composite Quantity)


View Dialogue

Enhance Article

Save Article

Like Article

View Dialogue

Enhance Article

Save Article

Like Article

Given a constructive integer N, the duty is to inform whether or not it’s an anti-prime quantity or not.

Anti-Prime Numbers (Extremely Composite Quantity):

A constructive integer that has extra divisors than any constructive quantity smaller than it, is known as an Anti-Prime Quantity (also referred to as Extremely Composite Quantity). 

Following is the checklist of the primary 10 anti-prime numbers together with their prime factorizations:

Anti-Prime Quantity Prime Factorization
1  
2 2
4 22
6 2×3
12 22×3
24 23×3
36 22×32
48 24×3
60 22×3×5
120 23×3×5

Examples:

Enter: N = 5040
Output: 5040 is anti-prime
Rationalization: There is no such thing as a constructive integer lower than 5040 having 
variety of divisors greater than or equal to the variety of divisors of 5040.

Enter: N = 72
Output: 72 just isn’t anti-prime

Strategy:

This query may be solved by counting the variety of divisors of the present quantity after which counting the variety of divisors for every quantity lower than it and checking whether or not any quantity has the variety of divisors higher than or equal to the variety of divisors of N.

Observe the steps to unravel this downside:

  • Discover what number of components this quantity has.
  • Now iterate until  N-1 and verify
    • Does any quantity lower than the quantity has components extra or equal to the  quantity 
    • If sure, then the quantity just isn’t an anti-prime quantity.
  • If in the long run not one of the numbers have the variety of divisors higher than or equal to the variety of divisors of N, then N is an anti-prime quantity.

Under is the implementation of the above strategy.

Java

class GFG {

  

    

    

    public static boolean isAntiPrime(int n)

    {

        int init = Divisors(n);

        for (int i = 1; i < n; i++) {

            if (Divisors(i) >= init)

  

                return false;

        }

        return true;

    }

  

    

    public static int Divisors(int a)

    {

        if (a == 1)

            return 1;

  

        

        int f = 2;

        for (int i = 2; i * i <= a; i++) {

            if (a % i == 0) {

                if (i * i != a) {

                    f += 2;

                }

                else

                    f++;

            }

        }

        return f;

    }

  

    

    public static void primary(String args[])

    {

        int N = 5040;

  

        

        if (isAntiPrime(N))

            System.out.println(N + " is anti-prime");

        else

            System.out.println(N + " just isn't anti-prime");

    }

}

Time Complexity: O(N3/2)
Auxiliary Area: O(1)

Leave a Reply

Your email address will not be published.