Given three integers L, R, and P where P is prime, the task is to count the number of times P occurs in the prime factorization of all numbers in the range [L, R].
Examples:
Input: L = 2, R = 8, P = 2
Output: 7
Element Prime Factors Time 2 occurs 2 2 1 3 3 0 4 2 * 2 2 5 5 0 6 2 * 3 1 7 7 0 8 2 * 2 * 2 3 1 + 0 + 2 + 0 + 1 + 0 + 3 = 7
Input: L = 5, R = 25, P = 7
Output: 3
Naive approach: Simply iterate over the range and for each value count how many times P divides that value and sum them up for the result. Time complexity O(R – L).
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <iostream>using namespace std;// Function to return the highest// power of p that divides nint countFactors(int n, int p){ int pwr = 0; while (n > 0 && n % p == 0) { n /= p; pwr++; } return pwr;}// Function to return the count of times p// appears in the prime factors of the// elements from the range [l, r]int getCount(int l, int r, int p){ // To store the required count int cnt = 0; // For every element of the range for (int i = l; i <= r; i++) { // Add the highest power of // p that divides i cnt += countFactors(i, p); } return cnt;}// Driver codeint main(){ int l = 2, r = 8, p = 2; cout << getCount(l, r, p); return 0;} |
Java
// Java implementation of the approachclass GFG {// Function to return the highest// power of p that divides nstatic int countFactors(int n, int p){ int pwr = 0; while (n > 0 && n % p == 0) { n /= p; pwr++; } return pwr;}// Function to return the count of times p// appears in the prime factors of the// elements from the range [l, r]static int getCount(int l, int r, int p){ // To store the required count int cnt = 0; // For every element of the range for (int i = l; i <= r; i++) { // Add the highest power of // p that divides i cnt += countFactors(i, p); } return cnt;}// Driver codepublic static void main(String[] args){ int l = 2, r = 8, p = 2; System.out.println(getCount(l, r, p));}} // This code is contributed by Rajput-Ji |
Python3
# Python3 implementation of the approach # Function to return the highest # power of p that divides n def countFactors(n, p) : pwr = 0; while (n > 0 and n % p == 0) : n //= p; pwr += 1; return pwr; # Function to return the count of times p # appears in the prime factors of the # elements from the range [l, r] def getCount(l, r, p) : # To store the required count cnt = 0; # For every element of the range for i in range(l, r + 1) : # Add the highest power of # p that divides i cnt += countFactors(i, p); return cnt; # Driver code if __name__ == "__main__" : l = 2; r = 8; p = 2; print(getCount(l, r, p)); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the approachusing System;class GFG {// Function to return the highest// power of p that divides nstatic int countFactors(int n, int p){ int pwr = 0; while (n > 0 && n % p == 0) { n /= p; pwr++; } return pwr;}// Function to return the count of times p// appears in the prime factors of the// elements from the range [l, r]static int getCount(int l, int r, int p){ // To store the required count int cnt = 0; // For every element of the range for (int i = l; i <= r; i++) { // Add the highest power of // p that divides i cnt += countFactors(i, p); } return cnt;}// Driver codepublic static void Main(String[] args){ int l = 2, r = 8, p = 2; Console.WriteLine(getCount(l, r, p));}}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript implementation of the approach// Function to return the highest// power of p that divides nfunction countFactors(n, p){ let pwr = 0; while (n > 0 && n % p == 0) { n /= p; pwr++; } return pwr;}// Function to return the count of times p// appears in the prime factors of the// elements from the range [l, r]function getCount(l, r, p){ // To store the required count let cnt = 0; // For every element of the range for (let i = l; i <= r; i++) { // Add the highest power of // p that divides i cnt += countFactors(i, p); } return cnt;}// Driver code let l = 2, r = 8, p = 2; document.write(getCount(l, r, p));</script> |
Output:
7
Time complexity : O((r-l+1)*log p) because the for loop runs (r-l+1) times and each iteration of the loop takes log p time due to the countFactors() function.
Auxiliary Space: O(1)
Efficient approach: Count the values which are divisible by P, P2, P3, …, Px in the range [L, R] where x is the largest power of P such that Px lies within the upper bound (Px ? N). Each iteration cost O(1) time thus time complexity becomes O(x) where x = (log(R) / log(P)).
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <iostream>using namespace std;// Function to return the count of times p// appears in the prime factors of the// elements from the range [l, r]int getCount(int l, int r, int p){ // To store the required count int cnt = 0; int val = p; while (1) { // Number of values in the range [0, r] // that are divisible by val int a = r / val; // Number of values in the range [0, l - 1] // that are divisible by val int b = (l - 1) / val; // Increment the power of the val val *= p; // (a - b) is the count of numbers in the // range [l, r] that are divisible by val if (a - b) { cnt += (a - b); } // No values that are divisible by val // thus exiting from the loop else break; } return cnt;}// Driver codeint main(){ int l = 2, r = 8, p = 2; cout << getCount(l, r, p); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG {// Function to return the count of times p// appears in the prime factors of the// elements from the range [l, r]static int getCount(int l, int r, int p){ // To store the required count int cnt = 0; int val = p; while (true) { // Number of values in the range [0, r] // that are divisible by val int a = r / val; // Number of values in the range [0, l - 1] // that are divisible by val int b = (l - 1) / val; // Increment the power of the val val *= p; // (a - b) is the count of numbers in the // range [l, r] that are divisible by val if ((a - b) > 0) { cnt += (a - b); } // No values that are divisible by val // thus exiting from the loop else break; } return cnt;}// Driver codepublic static void main(String[] args){ int l = 2, r = 8, p = 2; System.out.println(getCount(l, r, p));}} // This code is contributed by 29AjayKumar |
Python3
# Python3 implementation of the approach# Function to return the count of times p# appears in the prime factors of the# elements from the range [l, r]def getCount(l, r, p): # To store the required count cnt = 0; val = p; while (True): # Number of values in the range [0, r] # that are divisible by val a = r // val; # Number of values in the range [0, l - 1] # that are divisible by val b = (l - 1) // val; # Increment the power of the val val *= p; # (a - b) is the count of numbers in the # range [l, r] that are divisible by val if (a - b): cnt += (a - b); # No values that are divisible by val # thus exiting from the loop else: break; return int(cnt);# Driver Codel = 2;r = 8;p = 2;print(getCount(l, r, p));# This code is contributed by princiraj |
C#
// C# implementation of the approachusing System; class GFG {// Function to return the count of times p// appears in the prime factors of the// elements from the range [l, r]static int getCount(int l, int r, int p){ // To store the required count int cnt = 0; int val = p; while (true) { // Number of values in the range [0, r] // that are divisible by val int a = r / val; // Number of values in the range [0, l - 1] // that are divisible by val int b = (l - 1) / val; // Increment the power of the val val *= p; // (a - b) is the count of numbers in the // range [l, r] that are divisible by val if ((a - b) > 0) { cnt += (a - b); } // No values that are divisible by val // thus exiting from the loop else break; } return cnt;}// Driver codepublic static void Main(String[] args){ int l = 2, r = 8, p = 2; Console.WriteLine(getCount(l, r, p));}}// This code is contributed by PrinciRaj1992 |
Javascript
<script>// Javascript implementation of the approach// Function to return the count of times p// appears in the prime factors of the// elements from the range [l, r]function getCount(l, r, p){ // To store the required count let cnt = 0; let val = p; while (1) { // Number of values in the range [0, r] // that are divisible by val let a = parseInt(r / val); // Number of values in the range [0, l - 1] // that are divisible by val let b = parseInt((l - 1) / val); // Increment the power of the val val *= p; // (a - b) is the count of numbers in the // range [l, r] that are divisible by val if (a - b) { cnt += (a - b); } // No values that are divisible by val // thus exiting from the loop else break; } return cnt;}// Driver code let l = 2, r = 8, p = 2; document.write(getCount(l, r, p));</script> |
Output:
7
Time complexity: O(log(r) * log(r))
Auxiliary Space: O(1)
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!
