Count Pronic numbers from a given range

0 0 7 minutes read

Given two integers A and B, the task is to count the number of pronic numbers that are present in the range [A, B].

Examples:

Input: A = 3, B = 20
Output: 3
Explanation: The pronic numbers from the range [3, 20] are 6, 12, 20

Input: A = 5000, B = 990000000
Output: 31393

Naive Approach: Follow the given steps to solve the problem:

Initialize the count of pronic numbers to 0.
For every number in the range [A, B], check whether it is a pronic integer or not
If found to be true, increment the count.
Finally, print the count

Below is the implementation of the above approach:

C++14

// 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

// 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

# 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#

// 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.

Javascript

<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>

Output:

Time Complexity: O((B – A) * ?(B – A))
Auxiliary Space: O(1)

Efficient Approach: Follow the below steps to solve the problem:

Define a function pronic(N) to find the count of pronic integers which are ? N.
Calculate the square root of N, say X.
If product of X and X – 1 is less than or equal to N, return N.
Otherwise, return N – 1.
Print pronic(B) – pronic(A – 1) to get the count of pronic integers in the range [A, B]