Count numbers from a given range having exactly 5 distinct factors

0 0 6 minutes read

Given two integers L and R, the task is to calculate the count of numbers from the range [L, R] having exactly 5 distinct positive factors.

Examples:

Input: L = 1, R= 100
Output: 2
Explanation: The only two numbers in the range [1, 100] having exactly 5 distinct factors are 16 and 81.
Factors of 16 are {1, 2, 4, 8, 16}.
Factors of 81 are {1, 3, 9, 27, 81}.

Input: L = 1, R= 100
Output: 2

Naive Approach: The simplest approach to solve this problem is to traverse the range [L, R] and for every number, count its factors. If the count of factors is equal to 5, increment count by 1.
Time Complexity: (R – L) × ?N
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the following observation needs to be made regarding numbers having exactly 5 factors.

Let the prime factorization of a number be p₁^a_¹×p₂^a_² × … ×p_n^a_ⁿ.
Therefore, the count of factors of this number can be written as (a₁ + 1)×(a₂ + 1)× … ×(a_n + 1).
Since this product must be equal to 5 (which is a prime number), only one term greater than 1 must exist in the product. That term must be equal to 5.
Therefore, if a_i + 1 = 5
=> a_i = 4

Follow the steps below to solve the problem:

The required count is the count of numbers in the range containing p⁴ as a factor, where p is a prime number.
For efficiently calculating p⁴ for a large range ([1, 10¹⁸]), the idea is to use Sieve of Eratosthenes to store all prime numbers up to 10^4.5.

Below is the implementation of the above approach:

C++14

// C++ Program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
const int N = 2e5;
 
// Stores all prime numbers
// up to 2 * 10^5
vector<long long> prime;
 
// Function to generate all prime
// numbers up to 2 * 10 ^ 5 using
// Sieve of Eratosthenes
void Sieve()
{
    prime.clear();
    vector<bool> p(N + 1, true);
 
    // Mark 0 and 1 as non-prime
    p[0] = p[1] = false;
 
    for (int i = 2; i * i <= N; i++) {
 
        // If i is prime
        if (p[i] == true) {
 
            // Mark all its factors as non-prime
            for (int j = i * i; j <= N; j += i) {
                p[j] = false;
            }
        }
    }
 
    for (int i = 1; i < N; i++) {
 
        // If current number is prime
        if (p[i]) {
 
            // Store the prime
            prime.push_back(1LL * pow(i, 4));
        }
    }
}
 
// Function to count numbers in the
// range [L, R] having exactly 5 factors
void countNumbers(long long int L,
                  long long int R)
{
 
    // Stores the required count
    int Count = 0;
 
    for (int p : prime) {
 
        if (p >= L && p <= R) {
            Count++;
        }
    }
    cout << Count << endl;
}
 
// Driver Code
int main()
{
    long long L = 16, R = 85000;
 
    Sieve();
 
    countNumbers(L, R);
 
    return 0;
}

Java

// Java Program to implement
// the above approach
import java.util.*; 
class GFG 
{
  static int N = 200000;
 
  // Stores all prime numbers
  // up to 2 * 10^5
  static int prime[] = new int [20000];
  static int index = 0;
 
  // Function to generate all prime
  // numbers up to 2 * 10 ^ 5 using
  // Sieve of Eratosthenes
  static void Sieve()
  {
    index = 0;
    int p[] = new int [N + 1];
    for(int i = 0; i <= N; i++)
    {
      p[i] = 1;
    }
 
    // Mark 0 and 1 as non-prime
    p[0] = p[1] = 0;
    for (int i = 2; i * i <= N; i++) 
    {
 
      // If i is prime
      if (p[i] == 1)
      {
 
        // Mark all its factors as non-prime
        for (int j = i * i; j <= N; j += i)
        {
          p[j] = 0;
        }
      }
    }
    for (int i = 1; i < N; i++)
    {
 
      // If current number is prime
      if (p[i] == 1)
      {
 
        // Store the prime
        prime[index++] = (int)(Math.pow(i, 4));
      }
    }
  }
 
  // Function to count numbers in the
  // range [L, R] having exactly 5 factors
  static void countNumbers(int L,int R)
  {
 
    // Stores the required count
    int Count = 0;
    for(int i = 0; i < index; i++)
    {
      int p = prime[i];
      if (p >= L && p <= R)
      {
        Count++;
      }
    }
    System.out.println(Count);
  }
 
  // Driver Code
  public static void main(String[] args) 
  {
    int L = 16, R = 85000;
    Sieve();
    countNumbers(L, R);
  }
}
 
// This code is contributed by amreshkumar3.

Python3

# Python3 implementation of
# the above approach 
N = 2 * 100000
 
# Stores all prime numbers
# up to 2 * 10^5
prime = [0] * N
 
# Function to generate all prime
# numbers up to 2 * 10 ^ 5 using
# Sieve of Eratosthenes
def Sieve() :
    p = [True] * (N + 1)
 
    # Mark 0 and 1 as non-prime
    p[0] = p[1] = False
    i = 2
    while(i * i <= N) :
 
        # If i is prime
        if (p[i] == True) :
 
            # Mark all its factors as non-prime
            for j in range(i * i, N, i):
                p[j] = False    
        i += 1
    for i in range(N):
 
        # If current number is prime
        if (p[i] != False) :
 
            # Store the prime
            prime.append(pow(i, 4))
 
# Function to count numbers in the
# range [L, R] having exactly 5 factors
def countNumbers(L, R) :
 
    # Stores the required count
    Count = 0
    for p in prime :
        if (p >= L and p <= R) :
            Count += 1
    print(Count)
 
# Driver Code
L = 16
R = 85000
Sieve()
countNumbers(L, R)
 
# This code is contributed by code_hunt.

C#

// C# Program to implement
// the above approach
using System;
class GFG 
{
  static int N = 200000;
 
  // Stores all prime numbers
  // up to 2 * 10^5
  static int []prime = new int [20000];
  static int index = 0;
 
  // Function to generate all prime
  // numbers up to 2 * 10 ^ 5 using
  // Sieve of Eratosthenes
  static void Sieve()
  {
    index = 0;
    int []p = new int [N + 1];
    for(int i = 0; i <= N; i++)
    {
      p[i] = 1;
    }
 
    // Mark 0 and 1 as non-prime
    p[0] = p[1] = 0;
    for (int i = 2; i * i <= N; i++) 
    {
 
      // If i is prime
      if (p[i] == 1)
      {
 
        // Mark all its factors as non-prime
        for (int j = i * i; j <= N; j += i)
        {
          p[j] = 0;
        }
      }
    }
    for (int i = 1; i < N; i++)
    {
 
      // If current number is prime
      if (p[i] == 1)
      {
 
        // Store the prime
        prime[index++] = (int)(Math.Pow(i, 4));
      }
    }
  }
 
  // Function to count numbers in the
  // range [L, R] having exactly 5 factors
  static void countNumbers(int L,int R)
  {
 
    // Stores the required count
    int Count = 0;
    for(int i = 0; i < index; i++)
    {
      int p = prime[i];
      if (p >= L && p <= R)
      {
        Count++;
      }
    }
    Console.WriteLine(Count);
  }
 
  // Driver Code
  public static void Main(String[] args) 
  {
    int L = 16, R = 85000;
    Sieve();
    countNumbers(L, R);
  }
}
 
// This code is contributed by shikhasingrajput

Javascript

<script>
// javascript program of the above approach
 
let N = 200000;
  
  // Stores all prime numbers
  // up to 2 * 10^5
  let prime = new Array(20000).fill(0); 
  let index = 0;
  
  // Function to generate all prime
  // numbers up to 2 * 10 ^ 5 using
  // Sieve of Eratosthenes
  function Sieve()
  {
    index = 0;
    let p = new Array (N + 1).fill(0); 
    for(let i = 0; i <= N; i++)
    {
      p[i] = 1;
    }
  
    // Mark 0 and 1 as non-prime
    p[0] = p[1] = 0;
    for (let i = 2; i * i <= N; i++)
    {
  
      // If i is prime
      if (p[i] == 1)
      {
  
        // Mark all its factors as non-prime
        for (let j = i * i; j <= N; j += i)
        {
          p[j] = 0;
        }
      }
    }
    for (let i = 1; i < N; i++)
    {
  
      // If current number is prime
      if (p[i] == 1)
      {
  
        // Store the prime
        prime[index++] = (Math.pow(i, 4));
      }
    }
  }
  
  // Function to count numbers in the
  // range [L, R] having exactly 5 factors
  function countNumbers(L, R)
  {
  
    // Stores the required count
    let Count = 0;
    for(let i = 0; i < index; i++)
    {
      let p = prime[i];
      if (p >= L && p <= R)
      {
        Count++;
      }
    }
    document.write(Count);
  }
 
    // Driver Code
     
    let L = 16, R = 85000;
    Sieve();
    countNumbers(L, R);
 
</script>

Output:

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

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!