Recuento de los divisores no primos de un número dado

Dado un número N , la tarea es encontrar el número de divisores no primos del número N dado.

Ejemplos:

Entrada: N = 8
Salida: 3
Explicación:
Los divisores de 8 son: {1, 2, 4, 8}
Divisores no primos: {1, 4, 8}

Entrada: N = 20
Salida: 4
Explicación:
Los divisores de 20 son: {1, 2, 4, 5, 10, 20}
Divisores no primos: {1, 4, 10, 20}

Enfoque: La observación clave en el problema es que cualquier número puede escribirse como un producto de sus factores primos como

$N=\prod_{i=1}^Ka_{i}^{b_i}$

donde K es el conteo de los factores primos del número dado. Usando permutación y combinación podemos encontrar que la cuenta total de los
factores que son

$\prod_{i=1}^k{(b_i + 1)}$

Por lo tanto, la cuenta de los factores no primos será:

$\text{Count of Non-prime factors = } \prod_{i=1}^k{(b_i + 1)} - k$

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program to find count of
// non-prime divisors of given number
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to factors of the given
// number
vector<int> getFactorization(int x)
{
    int count = 0;
    vector<int> v;
 
    // Loop to find the divisors of
    // the number 2
    while (x % 2 == 0) {
        count++;
        x = x / 2;
    }
    if (count != 0)
        v.push_back(count);
 
    // Loop to find the divisors of the
    // given number upto SQRT(N)
    for (int i = 3; i <= sqrt(x); i += 2) {
        count = 0;
        while (x % i == 0) {
            count++;
            x /= i;
        }
        if (count != 0)
            v.push_back(count);
    }
 
    // Condition to check if the rest
    // number is also a prime number
    if (x > 1) {
        v.push_back(1);
    }
    return v;
}
 
// Function to find the non-prime
// divisors of the given number
int nonPrimeDivisors(int N)
{
    vector<int> v = getFactorization(N);
    int ret = 1;
 
    // Loop to count the number of
    // the total divisors of given number
    for (int i = 0; i < v.size(); i++)
        ret = ret * (v[i] + 1);
 
    ret = ret - v.size();
    return ret;
}
 
// Driver Code
int main()
{
    int N = 8;
 
    // Function Call
    cout << nonPrimeDivisors(N) << endl;
    return 0;
}

Java

// Java program to find
// count of non-prime
// divisors of given number
import java.util.*;
class GFG{
 
// Function to factors
// of the given number
static Vector<Integer> getFactorization(int x)
{
  int count = 0;
  Vector<Integer> v = new Vector<>();
 
  // Loop to find the
  // divisors of the number 2
  while (x % 2 == 0)
  {
    count++;
    x = x / 2;
  }
   
  if (count != 0)
    v.add(count);
 
  // Loop to find the divisors
  // of the given number upto SQRT(N)
  for (int i = 3;
           i <= Math.sqrt(x); i += 2)
  {
    count = 0;
    while (x % i == 0)
    {
      count++;
      x /= i;
    }
     
    if (count != 0)
      v.add(count);
  }
 
  // Condition to check if
  // the rest number is also
  // a prime number
  if (x > 1)
  {
    v.add(1);
  }
  return v;
}
 
// Function to find the non-prime
// divisors of the given number
static int nonPrimeDivisors(int N)
{
  Vector<Integer> v = getFactorization(N);
  int ret = 1;
 
  // Loop to count the number of
  // the total divisors of given number
  for (int i = 0; i < v.size(); i++)
    ret = ret * (v.get(i) + 1);
 
  ret = ret - v.size();
  return ret;
}
 
// Driver Code
public static void main(String[] args)
{
  int N = 8;
 
  // Function Call
  System.out.println(nonPrimeDivisors(N));
}
}
 
// This code is contributed by shikhasingrajput

Python3

# Python3 program to find count of
# non-prime divisors of given number
from math import sqrt
 
# Function to factors of the given
# number
def getFactorization(x):
     
    count = 0
    v = []
 
    # Loop to find the divisors of
    # the number 2
    while (x % 2 == 0):
        count += 1
        x = x // 2
 
    if (count != 0):
        v.append(count)
 
    # Loop to find the divisors of the
    # given number upto SQRT(N)
    for i in range(3, int(sqrt(x)) + 12):
        count = 0
         
        while (x % i == 0):
            count += 1
            x //= i
             
        if (count != 0):
            v.append(count)
 
    # Condition to check if the rest
    # number is also a prime number
    if (x > 1):
        v.append(1)
         
    return v
 
# Function to find the non-prime
# divisors of the given number
def nonPrimeDivisors(N):
     
    v = getFactorization(N)
    ret = 1
 
    # Loop to count the number of
    # the total divisors of given number
    for i in range(len(v)):
        ret = ret * (v[i] + 1)
    ret = ret - len(v)
     
    return ret
 
# Driver Code
if __name__ == '__main__':
     
    N = 8
 
    # Function Call
    print(nonPrimeDivisors(N))
 
# This code is contributed by Samarth

C#

// C# program to find
// count of non-prime
// divisors of given number
using System;
using System.Collections.Generic;
class GFG{
 
// Function to factors
// of the given number
static List<int> getFactorization(int x)
{
  int count = 0;
  List<int> v = new List<int>();
 
  // Loop to find the
  // divisors of the number 2
  while (x % 2 == 0)
  {
    count++;
    x = x / 2;
  }
   
  if (count != 0)
    v.Add(count);
 
  // Loop to find the divisors
  // of the given number upto
  // SQRT(N)
  for (int i = 3;
           i <= Math.Sqrt(x); i += 2)
  {
    count = 0;
    while (x % i == 0)
    {
      count++;
      x /= i;
    }
     
    if (count != 0)
      v.Add(count);
  }
 
  // Condition to check if
  // the rest number is also
  // a prime number
  if (x > 1)
  {
    v.Add(1);
  }
  return v;
}
 
// Function to find the non-prime
// divisors of the given number
static int nonPrimeDivisors(int N)
{
  List<int> v = getFactorization(N);
  int ret = 1;
 
  // Loop to count the number of
  // the total divisors of given number
  for (int i = 0; i < v.Count; i++)
    ret = ret * (v[i] + 1);
 
  ret = ret - v.Count;
  return ret;
}
 
// Driver Code
public static void Main(String[] args)
{
  int N = 8;
 
  // Function Call
  Console.WriteLine(nonPrimeDivisors(N));
}
}
 
// This code is contributed by gauravrajput1

Javascript

<script>
 
// Javascript program to find
// count of non-prime
// divisors of given number
 
// Function to factors
// of the given number
function getFactorization(x)
{
      let count = 0;
      let v = [];
  
      // Loop to find the
      // divisors of the number 2
      while (x % 2 == 0)
      {
        count++;
        x = Math.floor(x / 2);
      }
    
      if (count != 0)
        v.push(count);
  
      // Loop to find the divisors
      // of the given number upto
      // SQRT(N)
      for (let i = 3;
        i <= Math.floor(Math.sqrt(x)); i += 2)
      {
        count = 0;
        while (x % i == 0)
        {
              count++;
              x = Math.floor(x / i);
        }
      
        if (count != 0)
          v.push(count);
      }
  
      // Condition to check if
      // the rest number is also
      // a prime number
      if (x > 1)
      {
        v.push(1);
      }
      return v;
}
  
// Function to find the non-prime
// divisors of the given number
function nonPrimeDivisors(N)
{
      let v = getFactorization(N);
      let ret = 1;
  
      // Loop to count the number of
      // the total divisors of given number
      for (let i = 0; i < v.length; i++)
        ret = ret * (v[i] + 1);
  
      ret = ret - v.length;
      return ret;
}
 
// Driver Code
     
    let N = 8;
  
  // Function Call
  document.write(nonPrimeDivisors(N));
     
</script>

Producción:

Publicación traducida automáticamente

Artículo escrito por manoj_26 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

C++

Java

Python3

C#

Javascript

Deja una respuesta Cancelar la respuesta