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

Опубликовано: 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 i ) = 0 . Таким образом, количество делителей умножается на (i + 1) . Количество делителей будет (i 1 + 1) * (i 2 + 1) *… * (i k + 1).
Теперь можно видеть, что может быть только один простой делитель для максимального i, и если N% p i = 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.

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