Cuente los números de Pronic de un rango dado

Dados dos enteros A y B , la tarea es contar el número de números pronicos que están presentes en el rango [A, B] .

Ejemplos:

Entrada: A = 3, B = 20
Salida: 3
Explicación: Los números pronicos del rango [3, 20] son ​​6, 12, 20

Entrada: A = 5000, B = 990000000
Salida: 31393

Enfoque ingenuo: siga los pasos dados para resolver el problema:

1. Inicializa el conteo de números pronicos a 0 .
2. Para cada número en el rango [A, B] , verifique si es un número entero pronico o no
3. Si se encuentra que es cierto, incremente el conteo.
4. Finalmente, imprima el conteo

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

// C++ program for
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if x
// is a Pronic Number or not
bool checkPronic(int x)
{
 
    for (int i = 0; i <= (int)(sqrt(x));
         i++) {
 
        // Check for Pronic Number by
        // multiplying consecutive
        // numbers
        if (x == i * (i + 1)) {
            return true;
        }
    }
    return false;
}
 
// Function to count pronic
// numbers in the range [A, B]
void countPronic(int A, int B)
{
    // Initialise count
    int count = 0;
 
    // Iterate from A to B
    for (int i = A; i <= B; i++) {
 
        // If i is pronic
        if (checkPronic(i)) {
 
            // Increment count
            count++;
        }
    }
 
    // Print count
    cout << count;
}
 
// Driver Code
int main()
{
    int A = 3, B = 20;
 
    // Function call to count pronic
    // numbers in the range [A, B]
    countPronic(A, B);
 
    return 0;
}

// Java program to implement
// the above approach
import java.util.*;
 
class GFG{
 
// Function to check if x
// is a Pronic Number or not
static boolean checkPronic(int x)
{
 
    for (int i = 0; i <= (int)(Math.sqrt(x));
         i++) {
 
        // Check for Pronic Number by
        // multiplying consecutive
        // numbers
        if ((x == i * (i + 1)) != false) {
            return true;
        }
    }
    return false;
}
 
// Function to count pronic
// numbers in the range [A, B]
static void countPronic(int A, int B)
{
    // Initialise count
    int count = 0;
 
    // Iterate from A to B
    for (int i = A; i <= B; i++) {
 
        // If i is pronic
        if (checkPronic(i) != false) {
 
            // Increment count
            count++;
        }
    }
 
    // Print count
    System.out.print(count);
}
 
// Driver Code
public static void main(String args[])
{
    int A = 3, B = 20;
 
    // Function call to count pronic
    // numbers in the range [A, B]
    countPronic(A, B);
}
}
 
// This code is contributed by sanjoy_62.

# Python3 program for the above approach
import math
 
# Function to check if x
# is a Pronic Number or not
def checkPronic(x) :
    for i in range(int(math.sqrt(x)) + 1):
 
        # Check for Pronic Number by
        # multiplying consecutive
        # numbers
        if (x == i * (i + 1)) :
            return True
    return False
   
# Function to count pronic
# numbers in the range [A, B]
def countPronic(A, B) :
     
    # Initialise count
    count = 0
 
    # Iterate from A to B
    for i in range(A, B + 1):
 
        # If i is pronic
        if (checkPronic(i) != 0) :
 
            # Increment count
            count += 1
         
    # Print count
    print(count)
 
# Driver Code
A = 3
B = 20
 
# Function call to count pronic
# numbers in the range [A, B]
countPronic(A, B)
 
# This code is contributed by susmitakundugoaldanga.

// C# program for the above approach
using System;
public class GFG
{
 
// Function to check if x
// is a Pronic Number or not
static bool checkPronic(int x)
{
 
    for (int i = 0; i <= (int)(Math.Sqrt(x));
         i++)
    {
 
        // Check for Pronic Number by
        // multiplying consecutive
        // numbers
        if ((x == i * (i + 1)) != false)
        {
            return true;
        }
    }
    return false;
}
 
// Function to count pronic
// numbers in the range [A, B]
static void countPronic(int A, int B)
{
   
    // Initialise count
    int count = 0;
 
    // Iterate from A to B
    for (int i = A; i <= B; i++)
    {
 
        // If i is pronic
        if (checkPronic(i) != false)
        {
 
            // Increment count
            count++;
        }
    }
 
    // Print count
    Console.Write(count);
}
 
 
// Driver Code
public static void Main(String[] args)
{
    int A = 3, B = 20;
 
    // Function call to count pronic
    // numbers in the range [A, B]
    countPronic(A, B);
}
}
 
// This code is contributed by code_hunt.

<script>
 
// Javascript program for
// the above approach
 
// Function to check if x
// is a Pronic Number or not
function checkPronic(x)
{
 
    for (let i = 0; i <= parseInt(Math.sqrt(x));
         i++) {
 
        // Check for Pronic Number by
        // multiplying consecutive
        // numbers
        if (x == i * (i + 1)) {
            return true;
        }
    }
    return false;
}
 
// Function to count pronic
// numbers in the range [A, B]
function countPronic(A, B)
{
    // Initialise count
    let count = 0;
 
    // Iterate from A to B
    for (let i = A; i <= B; i++) {
 
        // If i is pronic
        if (checkPronic(i)) {
 
            // Increment count
            count++;
        }
    }
 
    // Print count
    document.write(count);
}
 
// Driver Code
let A = 3, B = 20;
 
// Function call to count pronic
// numbers in the range [A, B]
countPronic(A, B);
 
</script>

3

Complejidad de Tiempo: O((B – A) * √(B – A))
Espacio Auxiliar: O(1)

Enfoque eficiente: siga los pasos a continuación para resolver el problema:

1. Defina una función pronic(N) para encontrar el conteo de enteros pronic que son ≤ N .
2. Calcula la raíz cuadrada de N , digamos X.
3. Si el producto de X y X – 1 es menor o igual que N , devuelve N .
4. De lo contrario, devuelve N – 1 .
5. Imprima pronic(B) – pronic(A – 1) para obtener el conteo de enteros pronic en el rango [A, B]

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count pronic
// numbers in the range [A, B]
int pronic(int num)
{
    // Check upto sqrt N
    int N = (int)sqrt(num);
 
    // If product of consecutive
    // numbers are less than equal to num
    if (N * (N + 1) <= num) {
        return N;
    }
 
    // Return N - 1
    return N - 1;
}
 
// Function to count pronic
// numbers in the range [A, B]
int countPronic(int A, int B)
{
    // Subtract the count of pronic numbers
    // which are <= (A - 1) from the count
    // f pronic numbers which are <= B
    return pronic(B) - pronic(A - 1);
}
 
// Driver Code
int main()
{
    int A = 3;
    int B = 20;
 
    // Function call to count pronic
    // numbers in the range [A, B]
    cout << countPronic(A, B);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
class GFG
{
 
// Function to count pronic
// numbers in the range [A, B]
static int pronic(int num)
{
   
    // Check upto sqrt N
    int N = (int)Math.sqrt(num);
 
    // If product of consecutive
    // numbers are less than equal to num
    if (N * (N + 1) <= num)
    {
        return N;
    }
 
    // Return N - 1
    return N - 1;
}
 
// Function to count pronic
// numbers in the range [A, B]
static int countPronic(int A, int B)
{
   
    // Subtract the count of pronic numbers
    // which are <= (A - 1) from the count
    // f pronic numbers which are <= B
    return pronic(B) - pronic(A - 1);
}
 
// Driver Code
public static void main(String[] args)
{
    int A = 3;
    int B = 20;
 
    // Function call to count pronic
    // numbers in the range [A, B]
    System.out.print(countPronic(A, B));
 
}
}
 
// This code is contributed by shikhasingrajput

# Python3 program for the above approach
 
# Function to count pronic
# numbers in the range [A, B]
def pronic(num) :
 
    # Check upto sqrt N
    N = int(num ** (1/2));
 
    # If product of consecutive
    # numbers are less than equal to num
    if (N * (N + 1) <= num) :
        return N;
 
    # Return N - 1
    return N - 1;
 
# Function to count pronic
# numbers in the range [A, B]
def countPronic(A, B) :
     
    # Subtract the count of pronic numbers
    # which are <= (A - 1) from the count
    # f pronic numbers which are <= B
    return pronic(B) - pronic(A - 1);
 
# Driver Code
if __name__ == "__main__" :
 
    A = 3;
    B = 20;
 
    # Function call to count pronic
    # numbers in the range [A, B]
    print(countPronic(A, B));
 
    # This code is contributed by AnkThon

// C# program for the above approach
using System;
public class GFG
{
 
// Function to count pronic
// numbers in the range [A, B]
static int pronic(int num)
{
   
    // Check upto sqrt N
    int N = (int)Math.Sqrt(num);
 
    // If product of consecutive
    // numbers are less than equal to num
    if (N * (N + 1) <= num)
    {
        return N;
    }
 
    // Return N - 1
    return N - 1;
}
 
// Function to count pronic
// numbers in the range [A, B]
static int countPronic(int A, int B)
{
   
    // Subtract the count of pronic numbers
    // which are <= (A - 1) from the count
    // f pronic numbers which are <= B
    return pronic(B) - pronic(A - 1);
}
 
// Driver Code
public static void Main(String[] args)
{
    int A = 3;
    int B = 20;
 
    // Function call to count pronic
    // numbers in the range [A, B]
    Console.Write(countPronic(A, B));
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
// Javascript program for the above approach
 
// Function to count pronic
// numbers in the range [A, B]
function pronic(num)
{
 
    // Check upto sqrt N
    var N = parseInt(Math.sqrt(num));
 
    // If product of consecutive
    // numbers are less than equal to num
    if (N * (N + 1) <= num) {
        return N;
    }
 
    // Return N - 1
    return N - 1;
}
 
// Function to count pronic
// numbers in the range [A, B]
function countPronic(A, B)
{
 
    // Subtract the count of pronic numbers
    // which are <= (A - 1) from the count
    // f pronic numbers which are <= B
    return pronic(B) - pronic(A - 1);
}
 
// Driver Code
var A = 3;
var B = 20;
 
// Function call to count pronic
// numbers in the range [A, B]
document.write(countPronic(A, B));
 
// This code is contributed by noob2000.
</script>

3

Complejidad de Tiempo: O(log ₂ (B))
Espacio Auxiliar: O(1)