Dado un número N, hallar el primer número triangular cuyo número de divisores sea superior a N. Los números triangulares son sumas de números naturales, es decir, de la forma x*(x+1)/2. Los primeros números triangulares son 1, 3, 6, 10, 15, 21, 28, …
Ejemplos:
Entrada : N = 2
Salida : 6
6 es el primer número triangular con más de 2 factores.
Entrada : N = 4
Salida : 28
Una solución ingenua es iterar para cada número triangular y contar el número de divisores usando el método Sieve. En cualquier momento, si el número de divisores excede el número N dado, obtenemos nuestra respuesta. Si el número triangular que tiene más de N divisores es X, entonces la complejidad temporal será O(X * sqrt(X)) ya que el procesamiento previo de números primos no es posible en el caso de números triangulares más grandes. Es importante entender la solución ingenua para resolver el problema de manera más eficiente.
Una solución eficiente será utilizar el hecho de que la fórmula del número triangular es x*(x+1)/2. La propiedad que usaremos es que k y k+1 son coprimos . Sabemos que dos coprimos tienen un conjunto distinto de factores primos. Habrá dos casos en los que X sea par e impar.
- Cuando X es par, entonces X/2 y (X+1) serán considerados como dos números cuya descomposición en factores primos se va a averiguar.
- Cuando X es impar, entonces X y (X+1)/2 se considerarán como dos números cuya descomposición en factores primos se va a averiguar.
Por lo tanto, el problema se ha reducido a solo encontrar la descomposición en factores primos de números más pequeños, lo que reduce significativamente la complejidad del tiempo. Podemos reutilizar la descomposición en factores primos para x+1 en las iteraciones posteriores y, por lo tanto, factorizar un número en cada iteración será suficiente. Iterando hasta que el número de divisores exceda N y considerando el caso de par e impar nos dará la respuesta.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ efficient program for counting the
// number of numbers <=N having exactly
// 9 divisors
#include <bits/stdc++.h>
using namespace std;
const int MAX = 100000;
// sieve method for prime calculation
bool prime[MAX + 1];
// Function to mark the primes
void sieve()
{
memset(prime, true, sizeof(prime));
// mark the primes
for (int p = 2; p * p < MAX; p++)
if (prime[p] == true)
// mark the factors of prime as non prime
for (int i = p * 2; i < MAX; i += p)
prime[i] = false;
}
// Function for finding no. of divisors
int divCount(int n)
{
// Traversing through all prime numbers
int total = 1;
for (int p = 2; p <= n; p++) {
if (prime[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 find the first triangular number
int findNumber(int n)
{
if (n == 1)
return 3;
// initial number
int i = 2;
// initial count of divisors
int count = 0;
// prestore the value
int second = 1;
int first = 1;
// iterate till we get the first triangular number
while (count <= n) {
// even
if (i % 2 == 0) {
// function call to count divisors
first = divCount(i + 1);
// multiply with previous value
count = first * second;
}
// odd step
else {
// function call to count divisors
second = divCount((i + 1) / 2);
// multiply with previous value
count = first * second;
}
i++;
}
return i * (i - 1) / 2;
}
// Driver Code
int main()
{
int n = 4;
// Call the sieve function for prime
sieve();
cout << findNumber(n);
return 0;
}
Java
// Java efficient program for counting the
// number of numbers <=N having exactly
// 9 divisors
public class GFG {
final static int MAX = 100000;
// sieve method for prime calculation
static boolean prime[] = new boolean [MAX + 1];
// Function to mark the primes
static void sieve()
{
for(int i = 0 ; i <= MAX ; i++)
prime[i] = true;
// mark the primes
for (int p = 2; p * p < MAX; p++)
if (prime[p] == true)
// mark the factors of prime as non prime
for (int i = p * 2; i < MAX; i += p)
prime[i] = false;
}
// Function for finding no. of divisors
static int divCount(int n)
{
// Traversing through all prime numbers
int total = 1;
for (int p = 2; p <= n; p++) {
if (prime[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 find the first triangular number
static int findNumber(int n)
{
if (n == 1)
return 3;
// initial number
int i = 2;
// initial count of divisors
int count = 0;
// prestore the value
int second = 1;
int first = 1;
// iterate till we get the first triangular number
while (count <= n) {
// even
if (i % 2 == 0) {
// function call to count divisors
first = divCount(i + 1);
// multiply with previous value
count = first * second;
}
// odd step
else {
// function call to count divisors
second = divCount((i + 1) / 2);
// multiply with previous value
count = first * second;
}
i++;
}
return i * (i - 1) / 2;
}
public static void main(String args[])
{
int n = 4;
// Call the sieve function for prime
sieve();
System.out.println(findNumber(n));
}
// This Code is contributed by ANKITRAI1
}
Python3
# Python 3 efficient program for counting the # number of numbers <=N having exactly # 9 divisors from math import sqrt MAX = 100000 prime = [ True for i in range(MAX + 1)] # Function to mark the primes def sieve(): # mark the primes k = int(sqrt(MAX)) for p in range(2,k,1): if (prime[p] == True): # mark the factors of prime as non prime for i in range(p * 2,MAX,p): prime[i] = False # Function for finding no. of divisors def divCount(n): # Traversing through all prime numbers total = 1 for p in range(2,n+1,1): if (prime[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 find the first triangular number def findNumber(n): if (n == 1): return 3 # initial number i = 2 # initial count of divisors count = 0 # prestore the value second = 1 first = 1 # iterate till we get the first triangular number while (count <= n): # even if (i % 2 == 0): # function call to count divisors first = divCount(i + 1) # multiply with previous value count = first * second # odd step else: # function call to count divisors second = divCount(int((i + 1) / 2)) # multiply with previous value count = first * second i += 1 return i * (i - 1) / 2 # Driver Code if __name__ == '__main__': n = 4 # Call the sieve function for prime sieve() print(int(findNumber(n))) # This code is contributed by # Surendra_Gangwar
C#
// C# efficient program for counting the
// number of numbers <=N having exactly
// 9 divisors
using System;
public class GFG {
static int MAX = 100000;
// sieve method for prime calculation
static bool[] prime = new bool [MAX + 1];
// Function to mark the primes
static void sieve()
{
for(int i = 0 ; i <= MAX ; i++)
prime[i] = true;
// mark the primes
for (int p = 2; p * p < MAX; p++)
if (prime[p] == true)
// mark the factors of prime as non prime
for (int i = p * 2; i < MAX; i += p)
prime[i] = false;
}
// Function for finding no. of divisors
static int divCount(int n)
{
// Traversing through all prime numbers
int total = 1;
for (int p = 2; p <= n; p++) {
if (prime[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 find the first triangular number
static int findNumber(int n)
{
if (n == 1)
return 3;
// initial number
int i = 2;
// initial count of divisors
int count = 0;
// prestore the value
int second = 1;
int first = 1;
// iterate till we get the first triangular number
while (count <= n) {
// even
if (i % 2 == 0) {
// function call to count divisors
first = divCount(i + 1);
// multiply with previous value
count = first * second;
}
// odd step
else {
// function call to count divisors
second = divCount((i + 1) / 2);
// multiply with previous value
count = first * second;
}
i++;
}
return i * (i - 1) / 2;
}
public static void Main()
{
int n = 4;
// Call the sieve function for prime
sieve();
Console.Write(findNumber(n));
}
}
PHP
<?php
// PHP efficient program for counting the
// number of numbers <=N having exactly
// 9 divisors
$MAX = 10000;
// sieve method for $prime calculation
$prime = array_fill(0, $MAX + 1, true);
// Function to mark the primes
function sieve()
{
global $prime;
global $MAX;
// mark the primes
for ($p = 2; $p * $p < $MAX; $p++)
if ($prime[$p] == true)
// mark the factors of prime
// as non prime
for ($i = $p * 2;
$i < $MAX; $i += $p)
$prime[$i] = false;
}
// Function for finding no. of divisors
function divCount($n)
{
global $prime;
// Traversing through all prime numbers
$total = 1;
for ($p = 2; $p <= $n; $p++)
{
if ($prime[$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++;
}
$total = $total * ($count + 1);
}
}
}
return $total;
}
// Function to find the first
// triangular number
function findNumber($n)
{
if ($n == 1)
return 3;
// initial number
$i = 2;
// initial count of divisors
$count = 0;
// prestore the value
$second = 1;
$first = 1;
// iterate till we get the
// first triangular number
while ($count <= $n)
{
// even
if ($i % 2 == 0)
{
// function call to $count divisors
$first = divCount($i + 1);
// multiply with previous value
$count = $first * $second;
}
// odd step
else
{
// function call to $count divisors
$second = divCount(($i + 1) / 2);
// multiply with previous value
$count = $first * $second;
}
$i++;
}
return $i * ($i - 1) / 2;
}
// Driver Code
$n = 4;
// Call the sieve function for prime
sieve();
echo findNumber($n);
// This code is contributed by ihritik
?>
Javascript
<script>
// javascript efficient program for counting the
// number of numbers <=N having exactly
// 9 divisors
const MAX = 100000;
// sieve method for prime calculation
let prime = new Array(MAX + 1).fill(0);
// Function to mark the primes
function sieve()
{
for (i = 0; i <= MAX; i++)
prime[i] = true;
// mark the primes
for (p = 2; p * p < MAX; p++)
if (prime[p] == true)
// mark the factors of prime as non prime
for (i = p * 2; i < MAX; i += p)
prime[i] = false;
}
// Function for finding no. of divisors
function divCount(n)
{
// Traversing through all prime numbers
var total = 1;
for (p = 2; p <= n; p++) {
if (prime[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
var count = 0;
if (n % p == 0) {
while (n % p == 0) {
n = n / p;
count++;
}
total = total * (count + 1);
}
}
}
return total;
}
// Function to find the first triangular number
function findNumber(n) {
if (n == 1)
return 3;
// initial number
var i = 2;
// initial count of divisors
var count = 0;
// prestore the value
var second = 1;
var first = 1;
// iterate till we get the first triangular number
while (count <= n) {
// even
if (i % 2 == 0) {
// function call to count divisors
first = divCount(i + 1);
// multiply with previous value
count = first * second;
}
// odd step
else {
// function call to count divisors
second = divCount((i + 1) / 2);
// multiply with previous value
count = first * second;
}
i++;
}
return i * (i - 1) / 2;
}
var n = 4;
// Call the sieve function for prime
sieve();
document.write(findNumber(n));
// This code contributed by Rajput-Ji
</script>
Producción
28
Complejidad de tiempo: O(N*logN),
- La criba de eratóstenes costará O(N*log(logN)) tiempo, pero
- estamos usando bucles anidados donde el bucle exterior atraviesa N veces y el bucle interior atraviesa logN veces, ya que en cada recorrido estamos decrementando por la división del piso del factor de n.
Espacio auxiliar: O(10 5 ), ya que estamos usando espacio adicional para la array de cebadores.