Un número N se llama altamente compuesto si tiene más divisores que cualquiera de los números más pequeños que N.
Pocos números altamente compuestos son:
1, 2, 4, 6, 12, 24, 36, 48, 60, 120….
Comprobar si N es un número altamente compuesto
Dado un número N , la tarea es verificar si N es un número altamente compuesto o no. Si N es un número altamente compuesto, imprima «Sí» , de lo contrario, imprima «No» .
Ejemplos:
Entrada: N = 60
Salida: Sí
60 es un compuesto altamente porque tiene 12 divisores
y ninguno de los números hasta 59 tiene 12 o más divisores.Entrada: N = 18
Salida: No
Acercarse:
- Encuentra el conteo de divisores de N
- Ahora, en un bucle de 1 a menos de N, verifique para cada i que si un número de divisores de i es mayor que la cuenta de divisores de N, entonces devuelva falso
- De lo contrario, devuelve verdadero al final.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation for checking
// Highly Composite Number
#include <bits/stdc++.h>
using namespace std;
// Function to count the number
// of divisors of the N
int divCount(int n)
{
// sieve method for prime calculation
bool hash[n + 1];
memset(hash, true, sizeof(hash));
for (int p = 2; p * p < n; p++)
if (hash[p] == true)
for (int i = p * 2; i < n; i += p)
hash[i] = false;
// Traversing through
// all prime numbers
int total = 1;
for (int p = 2; p <= n; p++) {
if (hash[p]) {
// calculate number of divisor
// with formula total div =
// (p1+1) * (p2+1) *.....* (pn+1)
// where n = (a1^p1)*(a2^p2)....
// *(an^pn) ai being prime divisor
// for n and pi are their respective
// power in factorization
int count = 0;
if (n % p == 0) {
while (n % p == 0) {
n = n / p;
count++;
}
total = total * (count + 1);
}
}
}
return total;
}
// Function to check if a number
// is a highly composite number
bool isHighlyCompositeNumber(int N)
{
// count number of factors of N
int NdivCount = divCount(N);
// loop to count number of factors of
// every number less than N
for (int i = 1; i < N; i++) {
int idivCount = divCount(i);
// If any number less than N has
// more factors than N,
// then return false
if (idivCount >= NdivCount)
return false;
}
return true;
}
// Driver code
int main()
{
// Given Number N
int N = 12;
// Function Call
if (isHighlyCompositeNumber(N))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java implementation for checking
// Highly Composite Number
import java.util.*;
class GFG{
// Function to count the number
// of divisors of the N
static int divCount(int n)
{
// sieve method for prime calculation
boolean []hash = new boolean[n + 1];
Arrays.fill(hash, true);
for (int p = 2; p * p < n; p++)
if (hash[p] == true)
for (int i = p * 2; i < n; i += p)
hash[i] = false;
// Traversing through
// all prime numbers
int total = 1;
for (int p = 2; p <= n; p++)
{
if (hash[p])
{
// calculate number of divisor
// with formula total div =
// (p1+1) * (p2+1) *.....* (pn+1)
// where n = (a1^p1)*(a2^p2)....
// *(an^pn) ai being prime divisor
// for n and pi are their respective
// power in factorization
int count = 0;
if (n % p == 0)
{
while (n % p == 0)
{
n = n / p;
count++;
}
total = total * (count + 1);
}
}
}
return total;
}
// Function to check if a number
// is a highly composite number
static boolean isHighlyCompositeNumber(int N)
{
// count number of factors of N
int NdivCount = divCount(N);
// loop to count number of factors of
// every number less than N
for (int i = 1; i < N; i++)
{
int idivCount = divCount(i);
// If any number less than N has
// more factors than N,
// then return false
if (idivCount >= NdivCount)
return false;
}
return true;
}
// Driver code
public static void main(String[] args)
{
// Given Number N
int N = 12;
// Function Call
if (isHighlyCompositeNumber(N))
System.out.print("Yes");
else
System.out.print("No");
}
}
// This code is contributed by gauravrajput1
Python3
# Python3 implementation for checking
# Highly Composite Number
# Function to count the number
# of divisors of the N
def divCount(n):
# Sieve method for prime calculation
Hash = [True for i in range(n + 1)]
p = 2
while ((p * p) < n):
if bool(Hash[p]):
i = p * 2
while i < n:
Hash[i] = False
i += p
p += 1
# Traversing through
# all prime numbers
total = 1
for P in range(2, n + 1):
if (bool(Hash[P])):
# Calculate number of divisor
# with formula total div =
# (p1+1) * (p2+1) *.....* (pn+1)
# where n = (a1^p1)*(a2^p2)....
# *(an^pn) ai being prime divisor
# for n and pi are their respective
# power in factorization
count = 0
if (n % P == 0):
while (n % P == 0):
n = n // P
count += 1
total = total * (count + 1)
return total
# Function to check if a number
# is a highly composite number
def isHighlyCompositeNumber(N):
# Count number of factors of N
NdivCount = divCount(N)
# Loop to count number of factors of
# every number less than N
for i in range(N):
idivCount = divCount(i)
# If any number less than N has
# more factors than N,
# then return false
if (idivCount >= NdivCount):
return bool(False)
return bool(True)
# Driver code
# Given Number N
N = 12
# Function Call
if (bool(isHighlyCompositeNumber(N))):
print("Yes")
else:
print("No")
# This code is contributed by divyeshrabadiya07
C#
// C# implementation for checking
// Highly Composite Number
using System;
class GFG{
// Function to count the number
// of divisors of the N
static int divCount(int n)
{
// sieve method for prime calculation
bool []hash = new bool[n + 1];
for(int i = 0; i < n + 1; i++)
hash[i] = true;
for (int p = 2; p * p < n; p++)
if (hash[p] == true)
for (int i = p * 2; i < n; i += p)
hash[i] = false;
// Traversing through
// all prime numbers
int total = 1;
for (int p = 2; p <= n; p++)
{
if (hash[p])
{
// calculate number of divisor
// with formula total div =
// (p1+1) * (p2+1) *.....* (pn+1)
// where n = (a1^p1)*(a2^p2)....
// *(an^pn) ai being prime divisor
// for n and pi are their respective
// power in factorization
int count = 0;
if (n % p == 0)
{
while (n % p == 0)
{
n = n / p;
count++;
}
total = total * (count + 1);
}
}
}
return total;
}
// Function to check if a number
// is a highly composite number
static bool isHighlyCompositeNumber(int N)
{
// count number of factors of N
int NdivCount = divCount(N);
// loop to count number of factors of
// every number less than N
for (int i = 1; i < N; i++)
{
int idivCount = divCount(i);
// If any number less than N has
// more factors than N,
// then return false
if (idivCount >= NdivCount)
return false;
}
return true;
}
// Driver code
public static void Main(String[] args)
{
// Given Number N
int N = 12;
// Function Call
if (isHighlyCompositeNumber(N))
Console.Write("Yes");
else
Console.Write("No");
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript implementation for checking
// Highly Composite Number
// Function to count the number
// of divisors of the N
function divCount( n) {
// sieve method for prime calculation
let hash = Array(n+1).fill(true);
for ( let p = 2; p * p < n; p++)
if (hash[p] == true)
for ( i = p * 2; i < n; i += p)
hash[i] = false;
// Traversing through
// all prime numbers
let total = 1;
for ( p = 2; p <= n; p++) {
if (hash[p]) {
// calculate number of divisor
// with formula total div =
// (p1+1) * (p2+1) *.....* (pn+1)
// where n = (a1^p1)*(a2^p2)....
// *(an^pn) ai being prime divisor
// for n and pi are their respective
// power in factorization
let count = 0;
if (n % p == 0) {
while (n % p == 0) {
n = n / p;
count++;
}
total = total * (count + 1);
}
}
}
return total;
}
// Function to check if a number
// is a highly composite number
function isHighlyCompositeNumber( N) {
// count number of factors of N
let NdivCount = divCount(N);
// loop to count number of factors of
// every number less than N
for ( let i = 1; i < N; i++) {
let idivCount = divCount(i);
// If any number less than N has
// more factors than N,
// then return false
if (idivCount >= NdivCount)
return false;
}
return true;
}
// Driver code
// Given Number N
let N = 12;
// Function Call
if (isHighlyCompositeNumber(N))
document.write("Yes");
else
document.write("No");
// This code contributed by Rajput-Ji
</script>
Producción:
Yes
Complejidad de tiempo: O(n)
Referencia : http://www.numbersaplenty.com/set/highly_composite_number/