Проверьте, есть ли у числа простое количество делителей

Опубликовано: 5 Января, 2022

Учитывая целое число N , задача состоит в том, чтобы проверить, является ли количество делителей числа N простым или нет.

Примеры:

Input: N = 13
Output: Yes
The divisor count is 2 (1 and 13) which is prime.
Input: N = 8
Output: No
The divisors are 1, 2, 4 and 8.

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход: прочтите эту статью, чтобы узнать количество делителей числа. Итак, найдите максимальное значение i для каждого простого делителя p такого, что N% (p ⁱ ) = 0 . Таким образом, количество делителей умножается на (i + 1) . Количество делителей будет (i ¹ + 1) * (i ² + 1) *… * (i ^k + 1).
Теперь можно видеть, что может быть только один простой делитель для максимального i, и если N% p ⁱ = 0, то (i + 1) должно быть простым. Простота может быть проверена во времени sqrt (n), а простые множители также могут быть найдены во времени sqrt (n) . Таким образом, общая временная сложность будет O (sqrt (n)) .

Ниже представлена реализация описанного выше подхода:

C ++

 // C++ implementation of the approach
 #include <bits/stdc++.h>
 using namespace std;
 // Function that returns true
 // if n is prime
 bool Prime( int n)
 {
    // There is no prime
    // less than 2
    if (n < 2)
        return false ; 
    // Run a loop from 2 to sqrt(n)
    for ( int i = 2; i <= sqrt (n); i++) 
        // If there is any factor
        if (n % i == 0)
            return false ; 
    return true ;
 }
 // Function that returns true if n
 // has a prime count of divisors
 bool primeCountDivisors( int n)
 {
    if (n < 2)
        return false ; 
    // Find the prime factors
    for ( int i = 2; i <= sqrt (n); i++)
        if (n % i == 0) { 
            // Find the maximum value of i for every
            // prime divisor p such that n % (p^i) == 0
            long a = n, c = 0;
            while (a % i == 0) {
                a /= i;
                c++;
            }
            // If c+1 is a prime number and a = 1
            if (a == 1 && Prime(c + 1))
                return true ; 
            // The number cannot have two factors
            // to have count of divisors prime
            else
                return false ;
        }
    // Else the number is prime so
    // it has only two divisors
    return true ;
 }
 // Driver code
 int main()
 {
    int n = 13; 
    if (primeCountDivisors(n))
        cout << "Yes" ;
    else
        cout << "No" ; 
    return 0;
 }

Джава

 // Java implementation of the approach
 class GFG
 {
    
    // Function that returns true
    // if n is prime
    static boolean Prime( int n)
    {
        // There is no prime
        // less than 2
        if (n < 2 )
            return false ;
    
        // Run a loop from 2 to sqrt(n)
        for ( int i = 2 ; i <= ( int )Math.sqrt(n); i++)
    
            // If there is any factor
            if (n % i == 0 )
                return false ;
        return true ;
    }
    
    // Function that returns true if n
    // has a prime count of divisors
    static boolean primeCountDivisors( int n)
    {
        if (n < 2 )
            return false ;
    
        // Find the prime factors
        for ( int i = 2 ; i <= ( int )Math.sqrt(n); i++)
            if (n % i == 0 )
            {
    
                // Find the maximum value of i for every
                // prime divisor p such that n % (p^i) == 0
                long a = n, c = 0 ;
                while (a % i == 0 )
                {
                    a /= i;
                    c++;
                }
    
                // If c+1 is a prime number and a = 1
                if (a == 1 && Prime(( int )c + 1 ) == true )
                    return true ;
    
                // The number cannot have two factors
                // to have count of divisors prime
                else
                    return false ;
            }
    
        // Else the number is prime so
        // it has only two divisors
        return true ;
    }
    
    // Driver code
    public static void main (String[] args)
    {
        int n = 13 ;
    
        if (primeCountDivisors(n))
            System.out.println( "Yes" );
        else
            System.out.println( "No" );
    }
 }
 // This code is contributed by AnkitRai01

Python3

 # Python3 implementation of the approach
 from math import sqrt
 # Function that returns true
 # if n is prime
 def Prime(n) : 
    # There is no prime
    # less than 2
    if (n < 2 ) :
        return False ; 
    # Run a loop from 2 to sqrt(n)
    for i in range ( 2 , int (sqrt(n)) + 1 ) : 
        # If there is any factor
        if (n % i = = 0 ) :
            return False ; 
    return True ;
 # Function that returns true if n
 # has a prime count of divisors
 def primeCountDivisors(n) : 
    if (n < 2 ) :
        return False ; 
    # Find the prime factors
    for i in range ( 2 , int (sqrt(n)) + 1 ) :
        if (n % i = = 0 ) : 
            # Find the maximum value of i for every
            # prime divisor p such that n % (p^i) == 0
            a = n; c = 0 ;
            while (a % i = = 0 ) :
                a / / = i;
                c + = 1 ; 
            # If c + 1 is a prime number and a = 1
            if (a = = 1 and Prime(c + 1 )) :
                return True ; 
            # The number cannot have two factors
            # to have count of divisors prime
            else :
                return False ;
        
    # Else the number is prime so
    # it has only two divisors
    return True ;
 # Driver code
 if __name__ = = "__main__" : 
    n = 13 ; 
    if (primeCountDivisors(n)) :
        print ( "Yes" );
    else :
        print ( "No" );
 # This code is contributed by AnkitRai01

C #

 // C# implementation of the approach
 using System;
 class GFG
 {
    
    // Function that returns true
    // if n is prime
    static bool Prime( int n)
    {
        
        // There is no prime
        // less than 2
        if (n < 2)
            return false ;
    
        // Run a loop from 2 to sqrt(n)
        for ( int i = 2; i <= ( int )Math.Sqrt(n); i++)
    
            // If there is any factor
            if (n % i == 0)
                return false ;
        return true ;
    }
    
    // Function that returns true if n
    // has a prime count of divisors
    static bool primeCountDivisors( int n)
    {
        if (n < 2)
            return false ;
    
        // Find the prime factors
        for ( int i = 2; i <= ( int )Math.Sqrt(n); i++)
            if (n % i == 0)
            {
    
                // Find the maximum value of i for every
                // prime divisor p such that n % (p^i) == 0
                long a = n, c = 0;
                while (a % i == 0)
                {
                    a /= i;
                    c++;
                }
    
                // If c+1 is a prime number and a = 1
                if (a == 1 && Prime(( int )c + 1) == true )
                    return true ;
    
                // The number cannot have two factors
                // to have count of divisors prime
                else
                    return false ;
            }
    
        // Else the number is prime so
        // it has only two divisors
        return true ;
    }
    
    // Driver code
    public static void Main()
    {
        int n = 13;
    
        if (primeCountDivisors(n))
            Console.WriteLine( "Yes" );
        else
            Console.WriteLine( "No" );
    }
 }
 // This code is contributed by AnkitRai01

Javascript

 <script>
 // Javascript implementation of the approach
 // Function that returns true
 // if n is prime
 function Prime(n)
 {
    
    // There is no prime
    // less than 2
    if (n < 2)
        return false ; 
    // Run a loop from 2 to sqrt(n)
    for ( var i = 2; i <= Math.sqrt(n); i++) 
        // If there is any factor
        if (n % i == 0)
            return false ; 
    return true ;
 }
 // Function that returns true if n
 // has a prime count of divisors
 function primeCountDivisors( n)
 {
    if (n < 2)
        return false ; 
    // Find the prime factors
    for ( var i = 2; i <= Math.sqrt(n); i++)
        if (n % i == 0)
        {
            
            // Find the maximum value of i for every
            // prime divisor p such that n % (p^i) == 0
            var a = n, c = 0;
            
            while (a % i == 0)
            {
                a /= i;
                c++;
            }
            // If c+1 is a prime number and a = 1
            if (a == 1 && Prime(c + 1))
                return true ; 
            // The number cannot have two factors
            // to have count of divisors prime
            else
                return false ;
        }
    // Else the number is prime so
    // it has only two divisors
    return true ;
 }
 // Driver rcode
 n = 13;
 if (primeCountDivisors(n))
    document.write( "Yes" );
 else
    document.write( "No" );
 // This code is contributed by SoumikMondal
 </script>

Выход:

 да

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене.

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Technical Scripter Олимпиады по программированию

Проверьте, есть ли у числа простое количество делителей

C ++

Джава

Python3

C #

Javascript

РЕКОМЕНДУЕМЫЕ СТАТЬИ