Count numbers up to N having exactly 5 divisors - Coding

Given a positive integer N, the task is to count the number of integers from the range [1, N] having exactly 5 divisors.

Examples:

Input: N = 18
Output: 1
Explanation:
From all the integers over the range [1, 18], 16 is the only integer that has exactly 5 divisors, i.e. 1, 2, 8, 4 and 16.
Therefore, the count of such integers is 1.

Input: N = 100
Output: 2

Naive Approach: The simplest approach to solve the given problem is to iterate over the range [1, N] and count those integers in this range having the count of divisors as 5.

C++

// C++ code for the approach

#include <iostream>
#include <cmath>

using namespace std;

void SieveOfEratosthenes(int n, bool prime[],
                         bool primesquare[], int a[]) {
     
    //For more details check out: /archive/sieve-of-eratosthenes/
     
    // Create a boolean array "prime[0..n]" and
    // initialize all entries it as true. A value
    // in prime[i] will finally be false if i is
    // Not a prime, else true.
    for (int i = 2; i <= n; i++)
        prime[i] = true;
 
    // Create a boolean array "primesquare[0..n*n+1]"
    // and initialize all entries it as false. A value
    // in squareprime[i] will finally be true if i is
    // square of prime, else false.
    for (int i = 0; i <= (n * n + 1); i++)
        primesquare[i] = false;
 
    // 1 is not a prime number
    prime[1] = false;
 
    for (int p = 2; p * p <= n; p++) {
        // If prime[p] is not changed, then
        // it is a prime
        if (prime[p] == true) {
            // Update all multiples of p starting from p * p
            for (int i = p * p; i <= n; i += p)
                prime[i] = false;
        }
    }
 
    int j = 0;
    for (int p = 2; p <= n; p++) {
        if (prime[p]) {
            // Storing primes in an array
            a[j] = p;
 
            // Update value in primesquare[p*p],
            // if p is prime.
            primesquare[p * p] = true;
            j++;
        }
    }
}
 
// Function to count divisors
int countDivisors(int n) {
    // If number is 1, then it will have only 1
    // as a factor. So, total factors will be 1.
    if (n == 1)
        return 1;
 
    bool prime[n + 1], primesquare[n * n + 1];
 
    int a[n]; // for storing primes upto n
 
    // Calling SieveOfEratosthenes to store prime
    // factors of n and to store square of prime
    // factors of n
    SieveOfEratosthenes(n, prime, primesquare, a);
 
    // ans will contain total number of distinct
    // divisors
    int ans = 1;
 
    // Loop for counting factors of n
    for (int i = 0;; i++) {
        // a[i] is not less than cube root n
        if (a[i] * a[i] * a[i] > n)
            break;
 
        // Calculating power of a[i] in n.
        int cnt = 1; // cnt is power of prime a[i] in n.
        while (n % a[i] == 0) // if a[i] is a factor of n
        {
            n = n / a[i];
            cnt = cnt + 1; // incrementing power
        }
 
        // Calculating the number of divisors
        // If n = a^p * b^q then total divisors of n
        // are (p+1)*(q+1)
        ans = ans * cnt;
    }
 
    // if a[i] is greater than cube root of n
 
    // First case
    if (prime[n])
        ans = ans * 2;
 
    // Second case
    else if (primesquare[n])
        ans = ans * 3;
 
    // Third case
    else if (n != 1)
        ans = ans * 4;
 
    return ans; // Total divisors
}

// Function to count the number of integers with exactly 5 divisors
int countIntegers(int n) {
      // Store count of numbers with exactly 5 divisors
      int count = 0;
  
    // loop from 1 to n to check its distinct count of divisors
      for (int i = 1; i <= n; i++) {
          // Function Call
        int divisors = countDivisors(i);
          
        // If the number of divisors is 5, check if it is a prime square
        if (divisors == 5 ) {
            count++;
        }
    }
  
    return count;
}

// Driver code
int main() {
    int n = 100;
    cout << countIntegers(n) << endl;
    return 0;
}

Java

// Java code for the approach

import java.util.Vector;

public class GFG {
    static void SieveOfEratosthenes(int n, boolean prime[],
                                    boolean primesquare[],
                                    int a[])
    {
        // Create a boolean array "prime[0..n]" and
        // initialize all entries it as true. A value
        // in prime[i] will finally be false if i is
        // Not a prime, else true.
        for (int i = 2; i <= n; i++)
            prime[i] = true;

        /* Create a boolean array "primesquare[0..n*n+1]"
         and initialize all entries it as false.
         A value in squareprime[i] will finally
         be true if i is square of prime,
         else false.*/
        for (int i = 0; i < ((n * n) + 1); i++)
            primesquare[i] = false;

        // 1 is not a prime number
        prime[1] = false;

        for (int p = 2; p * p <= n; p++) {
            // If prime[p] is not changed,
            // then it is a prime
            if (prime[p] == true) {
                // Update all multiples of p
                for (int i = p * 2; i <= n; i += p)
                    prime[i] = false;
            }
        }

        int j = 0;
        for (int p = 2; p <= n; p++) {
            if (prime[p]) {
                // Storing primes in an array
                a[j] = p;

                // Update value in
                // primesquare[p*p],
                // if p is prime.
                primesquare[p * p] = true;
                j++;
            }
        }
    }

    // Function to count divisors
    static int countDivisors(int n)
    {
        // If number is 1, then it will
        // have only 1 as a factor. So,
        // total factors will be 1.
        if (n == 1)
            return 1;

        boolean prime[] = new boolean[n + 1];
        boolean primesquare[] = new boolean[(n * n) + 1];

        // for storing primes upto n
        int a[] = new int[n];

        // Calling SieveOfEratosthenes to
        // store prime factors of n and to
        // store square of prime factors of n
        SieveOfEratosthenes(n, prime, primesquare, a);

        // ans will contain total number
        // of distinct divisors
        int ans = 1;

        // Loop for counting factors of n
        for (int i = 0;; i++) {
            // a[i] is not less than cube root n
            if (a[i] * a[i] * a[i] > n)
                break;

            // Calculating power of a[i] in n.
            // cnt is power of prime a[i] in n.
            int cnt = 1;

            // if a[i] is a factor of n
            while (n % a[i] == 0) {
                n = n / a[i];

                // incrementing power
                cnt = cnt + 1;
            }

            // Calculating the number of divisors
            // If n = a^p * b^q then total
            // divisors of n are (p+1)*(q+1)
            ans = ans * cnt;
        }

        // if a[i] is greater than cube root
        // of n

        // First case
        if (prime[n])
            ans = ans * 2;

        // Second case
        else if (primesquare[n])
            ans = ans * 3;

        // Third case
        else if (n != 1)
            ans = ans * 4;

        return ans; // Total divisors
    }

    // Function to count the number of integers with exactly
    // 5 divisors
    static int countIntegers(int n)
    {
        // Store count of numbers with exactly 5 divisors
        int count = 0;

        // loop from 1 to n to check its distinct count of
        // divisors
        for (int i = 1; i <= n; i++) {
            // Function Call
            int divisors = countDivisors(i);

            // If the number of divisors is 5, check if it
            // is a prime square
            if (divisors == 5) {
                count++;
            }
        }

        return count;
    }

    // Driver code
    public static void main(String[] args)
    {
        int N = 100;
        System.out.println(countIntegers(N));
    }
}

Python

# Python3 code for the approach

import math

def sieveOfEratosthenes(n):
    # Create a boolean array "prime[0..n]" and initialize
    # all entries it as true. A value in prime[i] will
    # finally be false if i is Not a prime, else true.
    prime = [True for i in range(n+1)]
    p = 2
    while(p * p <= n):
        # If prime[p] is not changed, then it is a prime
        if (prime[p] == True):
            # Update all multiples of p
            for i in range(p * p, n+1, p):
                prime[i] = False
        p += 1
 
    # Store prime numbers
    primes = []
    for p in range(2, n+1):
        if prime[p]:
            primes.append(p)
 
    return primes
 
# Function to count divisors
def countDivisors(n, primes):
    # If number is 1, then it will have only 1 as a factor.
    # So, total factors will be 1.
    if (n == 1):
        return 1
 
    ans = 1
 
    # Loop for counting factors of n
    i = 0
    while (primes[i] <= math.sqrt(n)):
        # a[i] is not less than square root of n
        cnt = 1 # cnt is power of prime a[i] in n.
        while (n % primes[i] == 0): # if a[i] is a factor of n
            n = n // primes[i]
            cnt += 1 # incrementing power
        ans = ans * cnt # Calculating the number of divisors
        i += 1
 
    # if a[i] is greater than square root of n
    if (n > 1):
        ans = ans * 2
 
    return ans # Total divisors
 
# Function to count the number of integers with exactly 5 divisors
def countIntegers(n):
    # Store count of numbers with exactly 5 divisors
    count = 0
  
    # Get all prime numbers up to n
    primes = sieveOfEratosthenes(n)
  
    # loop from 1 to n to check its distinct count of divisors
    for i in range(1, n+1):
        # Function Call
        divisors = countDivisors(i, primes)
          
        # If the number of divisors is 5, check if it is a prime square
        if (divisors == 5 and int(math.sqrt(i))**2 == i):
            count += 1
  
    return count
 
# Driver code
if __name__ == "__main__":
  # Input integer
  n = 100
  
  # Function call
  print(countIntegers(n))

using System;

public class GFG
{
    static void SieveOfEratosthenes(int n, bool[] prime,
                                    bool[] primesquare,
                                    int[] a)
    {
        // Create a boolean array "prime[0..n]" and
        // initialize all entries it as true. A value
        // in prime[i] will finally be false if i is
        // Not a prime, else true.
        for (int i = 2; i <= n; i++)
            prime[i] = true;

        /* Create a boolean array "primesquare[0..n*n+1]"
         and initialize all entries it as false.
         A value in squareprime[i] will finally
         be true if i is square of prime,
         else false.*/
        for (int i = 0; i < ((n * n) + 1); i++)
            primesquare[i] = false;

        // 1 is not a prime number
        prime[1] = false;

        for (int p = 2; p * p <= n; p++)
        {
            // If prime[p] is not changed,
            // then it is a prime
            if (prime[p] == true)
            {
                // Update all multiples of p
                for (int i = p * 2; i <= n; i += p)
                    prime[i] = false;
            }
        }

        int j = 0;
        for (int p = 2; p <= n; p++)
        {
            if (prime[p])
            {
                // Storing primes in an array
                a[j] = p;

                // Update value in
                // primesquare[p*p],
                // if p is prime.
                primesquare[p * p] = true;
                j++;
            }
        }
    }

    // Function to count divisors
    static int countDivisors(int n)
    {
        // If number is 1, then it will
        // have only 1 as a factor. So,
        // total factors will be 1.
        if (n == 1)
            return 1;

        bool[] prime = new bool[n + 1];
        bool[] primesquare = new bool[(n * n) + 1];

        // for storing primes upto n
        int[] a = new int[n];

        // Calling SieveOfEratosthenes to
        // store prime factors of n and to
        // store square of prime factors of n
        SieveOfEratosthenes(n, prime, primesquare, a);

        // ans will contain total number
        // of distinct divisors
        int ans = 1;

        // Loop for counting factors of n
        for (int i = 0; ; i++)
        {
            // a[i] is not less than cube root n
            if (a[i] * a[i] * a[i] > n)
                break;

            // Calculating power of a[i] in n.
            // cnt is power of prime a[i] in n.
            int cnt = 1;

            // if a[i] is a factor of n
            while (n % a[i] == 0)
            {
                n = n / a[i];

                // incrementing power
                cnt = cnt + 1;
            }

            // Calculating the number of divisors
            // If n = a^p * b^q then total
            // divisors of n are (p+1)*(q+1)
            ans = ans * cnt;
        }

        // if a[i] is greater than cube root
        // of n

        // First case
        if (prime[n])
            ans = ans * 2;

        // Second case
        else if (primesquare[n])
            ans = ans * 3;

        // Third case
        else if (n != 1)
            ans = ans * 4;

        return ans; // Total divisors
    }

    // Function to count the number of integers with exactly
    // 5 divisors
    static int countIntegers(int n)
    {
        // Store count of numbers with exactly 5 divisors
        int count = 0;

        // loop from 1 to n to check its distinct count of
        // divisors
        for (int i = 1; i <= n; i++)
        {
            // Function Call
            int divisors = countDivisors(i);

            // If the number of divisors is 5, check if it
            // is a prime square
            if (divisors == 5)
            {
                count++;
            }
        }

        return count;
    }

    // Driver code
    public static void Main(string[] args)
    {
        int N = 100;
        Console.WriteLine(countIntegers(N));
    }
}

JavaScript

function sieveOfEratosthenes(n)
{

  // Create a boolean array "prime[0..n]" and initialize
  // all entries it as true. A value in prime[i] will
  // finally be false if i is Not a prime, else true.
  let prime = new Array(n+1).fill(true);
  let p = 2;
  while(p * p <= n)
  {
  
    // If prime[p] is not changed, then it is a prime
    if (prime[p] == true)
    {
    
      // Update all multiples of p
      for (let i = p * p; i <= n; i += p) {
        prime[i] = false;
      }
    }
    p += 1;
  }

  // Store prime numbers
  let primes = [];
  for (let p = 2; p <= n; p++) {
    if (prime[p] == true) {
      primes.push(p);
    }
  }

  return primes;
}

// Function to count divisors
function countDivisors(n, primes) 
{

  // If number is 1, then it will have only 1 as a factor.
  // So, total factors will be 1.
  if (n == 1) {
    return 1;
  }

  let ans = 1;

  // Loop for counting factors of n
  let i = 0;
  while (primes[i] <= Math.sqrt(n))
  {
  
    // a[i] is not less than square root of n
    let cnt = 1; // cnt is power of prime a[i] in n.
    while (n % primes[i] == 0) { // if a[i] is a factor of n
      n = n / primes[i];
      cnt += 1; // incrementing power
    }
    ans = ans * cnt; // Calculating the number of divisors
    i += 1;
  }

  // if a[i] is greater than square root of n
  if (n > 1) {
    ans = ans * 2;
  }

  return ans; // Total divisors
}

// Function to count the number of integers with exactly 5 divisors
function countIntegers(n) {
  // Store count of numbers with exactly 5 divisors
  let count = 0;

  // Get all prime numbers up to n
  let primes = sieveOfEratosthenes(n);

  // loop from 1 to n to check its distinct count of divisors
  for (let i = 1; i <= n; i++)
  {
  
    // Function Call
    let divisors = countDivisors(i, primes);

    // If the number of divisors is 5, check if it is a prime square
    if (divisors == 5 && Math.sqrt(i)**2 == i) {
      count += 1;
    }
  }

  return count;
}

// Driver code
let n = 100;
console.log(countIntegers(n));

Output

Time Complexity: O(N^4/3)
Auxiliary Space: O(1)

Efficient Approach: The above approach can also be optimized by observing a fact that the numbers that have exactly 5 divisors can be expressed in the form of p⁴, where p is a prime number as the count of divisors is exactly 5. Follow the below steps to solve the problem:

Generate all primes such that their fourth power is less than 10¹⁸ by using Sieve of Eratosthenes and store it in vector, say A[].
Initialize two variables, say low as 0 and high as A.size() – 1.
For performing the Binary Search iterate until low is less than high and perform the following steps:
- Find the value of mid as the (low + high)/2.
- Find the value of fourth power of element at indices mid (mid – 1) and store it in a variable, say current and previous respectively.
- If the value of current is N, then print the value of A[mid] as the result.
- If the value of current is greater than N and previous is at most N, then print the value of A[mid] as the result.
- If the value of current is greater than N then update the value of high as (mid – 1). Otherwise, update the value of low as (mid + 1).

Below is the implementation of the above approach:

C++

// C++ program for the above approach

#include <bits/stdc++.h>
#define ll long long int
const int MAX = 1e5;
using namespace std;

// Function to calculate the value of
// (x^y) using binary exponentiation
ll power(ll x, unsigned ll y)
{
    // Stores the value of x^y
    ll res = 1;

    // Base Case
    if (x == 0)
        return 0;

    while (y > 0) {

        // If y is odd multiply
        // x with result
        if (y & 1)
            res = (res * x);

        // Otherwise, divide y by 2
        y = y >> 1;

        x = (x * x);
    }
    return res;
}

// Function to perform the Sieve Of
// Eratosthenes to find the prime
// number over the range [1, 10^5]
void SieveOfEratosthenes(
    vector<pair<ll, ll> >& v)
{
    bool prime[MAX + 1];

    memset(prime, true, sizeof(prime));

    prime[1] = false;

    for (int p = 2; p * p <= MAX; p++) {

        // If prime[p] is not changed
        // then it is a prime
        if (prime[p] == true) {

            // Set all the multiples of
            // p to non-prime
            for (int i = p * 2;
                 i <= MAX; i += p)
                prime[i] = false;
        }
    }

    int num = 1;

    // Iterate over the range [1, MAX]
    for (int i = 1; i <= MAX; i++) {

        // Store all the prime number
        if (prime[i]) {
            v.push_back({ i, num });
            num++;
        }
    }
}

// Function to find the primes having
// only 5 divisors
int countIntegers(ll n)
{
    // Base Case
    if (n < 16) {
        return 0;
    }

    // First value of the pair has the
    // prime number and the second value
    // has the count of primes till that
    // prime numbers
    vector<pair<ll, ll> > v;

    // Precomputing all the primes
    SieveOfEratosthenes(v);

    int low = 0;
    int high = v.size() - 1;

    // Perform the Binary search
    while (low <= high) {

        int mid = (low + high) / 2;

        // Calculate the fourth power of
        // the curr and prev
        ll curr = power(v[mid].first, 4);
        ll prev = power(v[mid - 1].first, 4);

        if (curr == n) {

            // Return value of mid
            return v[mid].second;
        }

        else if (curr > n and prev <= n) {

            // Return value of mid-1
            return v[mid - 1].second;
        }
        else if (curr > n) {

            // Update the value of high
            high = mid - 1;
        }

        else {

            // Update the value of low
            low = mid + 1;
        }
    }
    return 0;
}

// Driver Code
int main()
{
    ll N = 100;
    cout << countIntegers(N);

    return 0;
}

Java

// Java program for the above approach
import java.util.Vector;

public class GFG {
    static int MAX = (int)1e5;

    public static class pair {
        long first;
        long second;
        pair(long first, long second)
        {
            this.first = first;
            this.second = second;
        }
    }
    // Function to calculate the value of
    // (x^y) using binary exponentiation
    static long power(long x, long y)
    {
      
        // Stores the value of x^y
        long res = 1;

        // Base Case
        if (x == 0)
            return 0;

        while (y > 0) 
        {

            // If y is odd multiply
            // x with result
            if ((y & 1) == 1)
                res = (res * x);

            // Otherwise, divide y by 2
            y = y >> 1;

            x = (x * x);
        }
        return res;
    }

    // Function to perform the Sieve Of
    // Eratosthenes to find the prime
    // number over the range [1, 10^5]
    static void SieveOfEratosthenes(Vector<pair> v)
    {
        boolean prime[] = new boolean[MAX + 1];

        for (int i = 0; i < prime.length; i++) {
            prime[i] = true;
        }

        prime[1] = false;

        for (int p = 2; p * p <= MAX; p++) {

            // If prime[p] is not changed
            // then it is a prime
            if (prime[p] == true) {

                // Set all the multiples of
                // p to non-prime
                for (int i = p * 2; i <= MAX; i += p)
                    prime[i] = false;
            }
        }

        int num = 1;

        // Iterate over the range [1, MAX]
        for (int i = 1; i <= MAX; i++) {

            // Store all the prime number
            if (prime[i]) {
                v.add(new pair(i, num));
                num++;
            }
        }
    }

    // Function to find the primes having
    // only 5 divisors
    static long countIntegers(long n)
    {
        // Base Case
        if (n < 16) {
            return 0;
        }

        // First value of the pair has the
        // prime number and the second value
        // has the count of primes till that
        // prime numbers
        Vector<pair> v = new Vector<>();

        // Precomputing all the primes
        SieveOfEratosthenes(v);

        int low = 0;
        int high = v.size() - 1;

        // Perform the Binary search
        while (low <= high) {

            int mid = (low + high) / 2;

            // Calculate the fourth power of
            // the curr and prev
            long curr = power(v.get(mid).first, 4);
            long prev = power(v.get(mid - 1).first, 4);

            if (curr == n) {

                // Return value of mid
                return v.get(mid).second;
            }

            else if (curr > n && prev <= n) {

                // Return value of mid-1
                return v.get(mid - 1).second;
            }
            else if (curr > n) {

                // Update the value of high
                high = mid - 1;
            }

            else {

                // Update the value of low
                low = mid + 1;
            }
        }
        return 0;
    }

    // Driver code
    public static void main(String[] args)
    {
        long N = 100;
        System.out.println(countIntegers(N));
    }
}

// This code is contributed by abhinavjain194

Python

# Python program for the above approach

# Function to calculate the value of
# (x**y) using binary exponentiation
def power(x, y):
    # Stores the value of x**y
    res = 1
    # Base Case
    if x == 0:
        return 0

    while y > 0:
        # If y is  odd multiply
        # x with result
        if y&1:
            res = (res*x)

        # otherwise, divide y by 2
        y = y >> 1
        x = (x*x)
    return res


# Function to perform the Sieve of
# Eratosthenes to find the prime
# number over the range [1, 10^5]
def sieveofeartoshenes(vec):
    prime = []
    for i in range(pow(10, 5)+1):
        prime.append(True)
    prime[1] = False
    p = 2
    while (p * p <= pow(10, 5)):

        # If prime[p] is not
        # changed, then it is a prime
        if (prime[p] == True):

            # Updating all multiples of
            # to non-prime
            for i in range(p * p, pow(10, 5) + 1, p):
                prime[i] = False
        p += 1
    num = 1

    # Iterate over the range [1, pow(10, 5)]
    for i in range(1, pow(10, 5)+1):
        # Stores all the prime number
        if prime[i]:
            vec.append([i, num])
            num += 1

def count_integer(n):
    # Base Case
    if n < 16:
        return 0

        # First value of the pair has the
        # prime number and the second value
        # has the cont of primes till that
        # prime numbers

    vec = [[]]
    # precomputing all the primes
    sieveofeartoshenes(vec)
    low = 0
    high = len(vec)-1

    # perform the Binary Search
    while low <= high:
        mid = (low+high)//2
        # Calculate the fourth power of
        # the curr and prev
        curr = power(vec[mid][0], 4)
        prev = power(vec[mid-1][0], 4)

        if curr == n:
            # Return value of mid
            return vec[mid][1]

        elif curr > n and prev <= n:
            # Return value of mid-1
            return vec[mid-1][1]
        elif curr > n:
            # Update the value of low
            high = mid - 1

        else:
            # Update the value of high
            low = mid + 1

n = 100
ans = count_integer(n)
print(ans)

# This code is contributed by Aditya Sharma

// C# code to implement the approach

using System;
using System.Collections.Generic;

public class pair {
    public long first;
    public long second;
    public pair(long first, long second)
    {
        this.first = first;
        this.second = second;
    }
}

class GFG {
    static int MAX = (int)1e5;

    // Function to calculate the value of
    // (x^y) using binary exponentiation
    static long power(long x, long y)
    {

        // Stores the value of x^y
        long res = 1;

        // Base Case
        if (x == 0)
            return 0;

        while (y > 0) {

            // If y is odd multiply
            // x with result
            if ((y & 1) == 1)
                res = (res * x);

            // Otherwise, divide y by 2
            y = y >> 1;

            x = (x * x);
        }
        return res;
    }

    // Function to perform the Sieve Of
    // Eratosthenes to find the prime
    // number over the range [1, 10^5]
    static void SieveOfEratosthenes(List<pair> v)
    {
        bool[] prime = new bool[MAX + 1];

        for (int i = 0; i < prime.Length; i++) {
            prime[i] = true;
        }

        prime[1] = false;

        for (int p = 2; p * p <= MAX; p++) {

            // If prime[p] is not changed
            // then it is a prime
            if (prime[p] == true) {

                // Set all the multiples of
                // p to non-prime
                for (int i = p * 2; i <= MAX; i += p)
                    prime[i] = false;
            }
        }

        int num = 1;

        // Iterate over the range [1, MAX]
        for (int i = 1; i <= MAX; i++) {

            // Store all the prime number
            if (prime[i]) {
                v.Add(new pair(i, num));
                num++;
            }
        }
    }

    // Function to find the primes having
    // only 5 divisors
    static long countIntegers(long n)
    {
        // Base Case
        if (n < 16) {
            return 0;
        }

        // First value of the pair has the
        // prime number and the second value
        // has the count of primes till that
        // prime numbers
        List<pair> v = new List<pair>();

        // Precomputing all the primes
        SieveOfEratosthenes(v);

        int low = 0;
        int high = v.Count - 1;

        // Perform the Binary search
        while (low <= high) {

            int mid = (low + high) / 2;

            // Calculate the fourth power of
            // the curr and prev
            long curr = power(v[mid].first, 4);
            long prev = power(v[mid - 1].first, 4);

            if (curr == n) {

                // Return value of mid
                return v[mid].second;
            }

            else if (curr > n && prev <= n) {

                // Return value of mid-1
                return v[mid - 1].second;
            }
            else if (curr > n) {

                // Update the value of high
                high = mid - 1;
            }

            else {

                // Update the value of low
                low = mid + 1;
            }
        }
        return 0;
    }

    // Driver code
    public static void Main(string[] args)
    {
        long N = 100;
        Console.WriteLine(countIntegers(N));
    }
}

// This code is contributed by phasing17

JavaScript

// JavaScript program for the above approach

// Function to calculate the value of
// (x**y) using binary exponentiation
function power(x, y)
{

    // Stores the value of x**y
    let res = 1;
    
    // Base Case
    if (x === 0) {
        return 0;
    }

    while (y > 0) 
    {
    
        // If y is  odd multiply
        // x with result
        if (y&1) {
            res = (res*x);
        }

        // otherwise, divide y by 2
        y = y >> 1;
        x = (x*x);
    }
    return res;
}

// Function to perform the Sieve of
// Eratosthenes to find the prime
// number over the range [1, 10^5]
function sieveofeartoshenes(vec) {
    let prime = [];
    for (let i = 0; i <= Math.pow(10, 5)+1; i++) {
        prime.push(true);
    }
    prime[1] = false;
    let p = 2;
    while (p * p <= Math.pow(10, 5)) {

        // If prime[p] is not
        // changed, then it is a prime
        if (prime[p] === true) {

            // Updating all multiples of
            // to non-prime
            for (let i = p * p; i <= Math.pow(10, 5) + 1; i += p) {
                prime[i] = false;
            }
        }
        p += 1;
    }
    let num = 1;

    // Iterate over the range [1, pow(10, 5)]
    for (let i = 1; i <= Math.pow(10, 5)+1; i++) 
    {
    
        // Stores all the prime number
        if (prime[i]) {
            vec.push([i, num]);
            num += 1;
        }
    }
}

function count_integer(n) 
{

    // Base Case
    if (n < 16) {
        return 0;
    }

    // First value of the pair has the
    // prime number and the second value
    // has the cont of primes till that
    // prime numbers
    let vec = [[]];
    
    // precomputing all the primes
    sieveofeartoshenes(vec);
    let low = 0;
    let high = vec.length-1;

    // perform the Binary Search
    while (low <= high) 
    {
        let mid = (low+high)//2;
        
        // Calculate the fourth power of
        // the curr and prev
        let curr = power(vec[mid][0], 4);
        let prev = power(vec[mid-1][0], 4);

        if (curr === n)
        {
        
            // Return value of mid
            return vec[mid][1];
        } 
        else if (curr > n && prev <= n) 
        {
        
            // Return value of mid-1
            return vec[mid-1][1];
        } 
        else if (curr > n)
        {
        
            // Update the value of low
            high = mid - 1;
        } 
        else
        {
        
        // Update the value of high
            low = mid + 1
        }
    }
}

let n = 100
let ans = count_integer(n)
console.log(ans)

// This code is contributed by phasing17

Output

Time Complexity: O(N*log N)
Auxiliary Space: O(N)

Using Sieve of Eratosthenes:

Explanation:

The code counts the number of integers with exactly 5 divisors, which are primes whose fourth power is less than or equal to the given number N.
It first generates prime numbers up to sqrt(N) using the Sieve of Eratosthenes.
Then, it iterates through these primes and counts those whose fourth power satisfies the condition.

C++

#include <bits/stdc++.h>
#define ll long long
using namespace std;

// Function to count integers with exactly 5 divisors
int countIntegers(ll n) {
    // Base Case
    if (n < 16) {
        return 0;
    }

    int count = 0;
    ll limit = sqrt(n);
    vector<bool> isPrime(limit + 1, true);
    vector<int> primes;

    // Sieve of Eratosthenes to find primes up to sqrt(n)
    for (ll p = 2; p <= limit; ++p) {
        if (isPrime[p]) {
            primes.push_back(p);
            for (ll i = p * p; i <= limit; i += p) {
                isPrime[i] = false;
            }
        }
    }

    // Count primes whose fourth power is less than or equal to n
    for (int p : primes) {
        if ((ll)p * p * p * p <= n) {
            ++count;
        } else {
            break; // Primes are sorted, so no need to check further
        }
    }

    return count;
}

// Driver code
int main() {
    ll N = 100;
    cout << countIntegers(N);
    return 0;
}

Java

import java.util.ArrayList;

public class CountIntegers {
    // Function to count integers with exactly 5 divisors
    static int countIntegers(int n) {
        // Base Case
        if (n < 16) {
            return 0;
        }

        int count = 0;
        int limit = (int) Math.sqrt(n);
        boolean[] isPrime = new boolean[limit + 1];
        ArrayList<Integer> primes = new ArrayList<>();

        // Sieve of Eratosthenes to find primes up to sqrt(n)
        for (int p = 2; p <= limit; ++p) {
            if (!isPrime[p]) {
                primes.add(p);
                for (int i = p * p; i <= limit; i += p) {
                    isPrime[i] = true;
                }
            }
        }

        // Count primes whose fourth power is less than or equal to n
        for (int p : primes) {
            if ((long) p * p * p * p <= n) {
                ++count;
            } else {
                break; // Primes are sorted, so no need to check further
            }
        }

        return count;
    }

    // Driver code
    public static void main(String[] args) {
        int N = 100;
        System.out.println(countIntegers(N));
    }
}

Python

import math

# Function to count integers with exactly 5 divisors
def countIntegers(n):
    # Base Case
    if n < 16:
        return 0

    count = 0
    limit = int(math.sqrt(n))
    isPrime = [True] * (limit + 1)
    primes = []

    # Sieve of Eratosthenes to find primes up to sqrt(n)
    for p in range(2, limit + 1):
        if isPrime[p]:
            primes.append(p)
            for i in range(p * p, limit + 1, p):
                isPrime[i] = False

    # Count primes whose fourth power is less than or equal to n
    for p in primes:
        if p * p * p * p <= n:
            count += 1
        else:
            break  # Primes are sorted, so no need to check further

    return count

# Driver code
N = 100
print(countIntegers(N))

JavaScript

// Function to count integers with exactly 5 divisors
function countIntegers(n) {
    // Base Case
    if (n < 16) {
        return 0;
    }

    let count = 0;
    const limit = Math.sqrt(n);
    const isPrime = new Array(limit + 1).fill(true);
    const primes = [];

    // Sieve of Eratosthenes to find primes up to sqrt(n)
    for (let p = 2; p <= limit; ++p) {
        if (isPrime[p]) {
            primes.push(p);
            for (let i = p * p; i <= limit; i += p) {
                isPrime[i] = false;
            }
        }
    }

    // Count primes whose fourth power is less than or equal to n
    for (let p of primes) {
        if (p * p * p * p <= n) {
            ++count;
        } else {
            break; // Primes are sorted, so no need to check further
        }
    }

    return count;
}

// Driver code
let N = 100;
console.log(countIntegers(N));

Output

Time Complexity: O(sqrt(N))

Space Complexity: O(sqrt(N))

Python Solution:

C++

#include <cmath>
#include <iostream>

// Function to count divisors of a number
int countDivisors(int num)
{
    int count = 0;
    int sqrtNum = sqrt(num);
    for (int i = 1; i <= sqrtNum; i++) {
        if (num % i == 0) {
            count += (i != num / i) ? 2 : 1;
        }
    }
    return count;
}

// Function to count integers with 5 divisors
int countIntegers(int n)
{
    int count = 0;
    for (int num = 1; num <= n; num++) {
        if (countDivisors(num) == 5) {
            count++;
        }
    }
    return count;
}

// Test cases
int main()
{
    std::cout << countIntegers(100)
              << std::endl; // Output: 2
    return 0;
}

Java

public class Main {
    // Function to count divisors of a number
    static int countDivisors(int num)
    {
        int count = 0;
        int sqrtNum = (int)Math.sqrt(num);
        for (int i = 1; i <= sqrtNum; i++) {
            if (num % i == 0) {
                count += (i != num / i) ? 2 : 1;
            }
        }
        return count;
    }

    // Function to count integers with 5 divisors
    static int countIntegers(int n)
    {
        int count = 0;
        for (int num = 1; num <= n; num++) {
            if (countDivisors(num) == 5) {
                count++;
            }
        }
        return count;
    }

    // Test cases
    public static void main(String[] args)
    {
        System.out.println(countIntegers(100)); // Output: 2
    }
}

// This code is contributed by shivamgupta0987654321

Python

import math


def count_integers(n):
    # Function to count divisors of a number
    def count_divisors(num):
        count = 0
        sqrt_num = int(math.sqrt(num))
        for i in range(1, sqrt_num + 1):
            if num % i == 0:
                count += 2 if i != num // i else 1
        return count

    count = 0
    for num in range(1, n + 1):
        if count_divisors(num) == 5:
            count += 1
    return count


# Test cases
print(count_integers(100))  # Output: 2

JavaScript

// Function to count divisors of a number
function countDivisors(num) {
    let count = 0;
    const sqrtNum = Math.sqrt(num);
    for (let i = 1; i <= sqrtNum; i++) {
        if (num % i === 0) {
            count += (i !== num / i) ? 2 : 1;
        }
    }
    return count;
}

// Function to count integers with 5 divisors
function countIntegers(n) {
    let count = 0;
    for (let num = 1; num <= n; num++) {
        if (countDivisors(num) === 5) {
            count++;
        }
    }
    return count;
}

// Test cases
console.log(countIntegers(100)); // Output: 2

Output

Time Complexity: O(N*sqrt(N))

Auxiliary Space: O(1)

Reffered: https://www.geeksforgeeks.org

Searching

Related
Longest substring between any pair of occurrences ōf similar characters
Find the word from a given sentence having given word as prefix
Abstraction of Binary Search
Minimum possible value T such that at most D Partitions of the Array having at most sum T is possible
Check if an Array is made up of Subarrays of continuous repetitions of every distinct element

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	12