Count numbers from a given range having exactly 5 distinct factors
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^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> |
7
Time Complexity: O(N * log(log(N)) )
Auxiliary Space: O(N)