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 p1a1×p2a2 × … ×pnan.
Therefore, the count of factors of this number can be written as (a1 + 1)×(a2 + 1)× … ×(an + 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 ai + 1 = 5
=> ai = 4
Follow the steps below to solve the problem:
- The required count is the count of numbers in the range containing p4 as a factor, where p is a prime number.
- For efficiently calculating p4 for a large range ([1, 1018]), the idea is to use Sieve of Eratosthenes to store all prime numbers up to 104.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^5vector<long long> prime;// Function to generate all prime// numbers up to 2 * 10 ^ 5 using// Sieve of Eratosthenesvoid 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 factorsvoid 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 Codeint main(){ long long L = 16, R = 85000; Sieve(); countNumbers(L, R); return 0;} |
Java
// Java Program to implement// the above approachimport 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^5prime = [0] * N# Function to generate all prime# numbers up to 2 * 10 ^ 5 using# Sieve of Eratosthenesdef 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 factorsdef countNumbers(L, R) : # Stores the required count Count = 0 for p in prime : if (p >= L and p <= R) : Count += 1 print(Count)# Driver CodeL = 16R = 85000Sieve()countNumbers(L, R)# This code is contributed by code_hunt. |
C#
// C# Program to implement// the above approachusing 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 approachlet 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:
7
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
