Given a number N and a prime number P, the task is to find the sum of the largest divisors of each number in the range [1, N], which is not divisible by P.
Examples:
Input: N = 8, P = 2
Output: 22
Explanation: Numbers are in the range [1, 8].
Number Largest Divisor not divisible by P = 2
1 1
2 1
3 3
4 1
5 5
6 3
7 7
8 1
Sum of all divisors with given constraint = 22.Input: N = 10, P = 5
Output: 43
Explanation: Numbers are in the range [1, 8].
Number Largest Divisor not divisible by P = 5
1 1
2 2
3 3
4 4
5 1
6 6
7 7
8 8
9 9
10 2
Sum of all divisors with given constraint = 43
Naive Approach: The naive idea is to find the divisors for each number in the range [1, N] and find the largest divisors which is not divisible by P and those numbers. Print the sum of all those largest divisors.
Time Complexity: O(N3/2)
Auxiliary Space: O(1)
Efficient Approach: The idea is to observe that the largest divisor of a number N not divisible by P would be N itself if N is not divisible by P. Else the required divisor will be the same as that of N/P. Below are the steps:
- If N is not divisible by P, then the largest divisor will be N, add this to the final sum.
- If N is divisible by P, the required divisor will be the same as that of N/P.
- So, find the sum of all numbers which are not divisible by P and add to them divisors of those which are divisible by P separately.
- The total sum would be N*(N + 1)/2. Subtract the sum of those which are divisible by P and add their corresponding value by recursively calling the function to find the sum for N/P.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the sum of largest // divisors of numbers in range 1 to N // not divisible by prime number P int func( int N, int P) { // Total sum upto N int sumUptoN = (N * (N + 1) / 2); int sumOfMultiplesOfP; // If no multiple of P exist up to N if (N < P) { return sumUptoN; } // If only P itself is in the range // from 1 to N else if ((N / P) == 1) { return sumUptoN - P + 1; } // Sum of those that are divisible by P sumOfMultiplesOfP = ((N / P) * (2 * P + (N / P - 1) * P)) / 2; // Recursively function call to // find the sum for N/P return (sumUptoN + func(N / P, P) - sumOfMultiplesOfP); } // Driver Code int main() { // Given N and P int N = 10, P = 5; // Function Call cout << func(N, P) << "\n" ; return 0; } |
Java
// Java program for the above approach import java.io.*; public class GFG{ // Function to find the sum of largest // divisors of numbers in range 1 to N // not divisible by prime number P static int func( int N, int P) { // Total sum upto N int sumUptoN = (N * (N + 1 ) / 2 ); int sumOfMultiplesOfP; // If no multiple of P exist up to N if (N < P) { return sumUptoN; } // If only P itself is in the range // from 1 to N else if ((N / P) == 1 ) { return sumUptoN - P + 1 ; } // Sum of those that are divisible by P sumOfMultiplesOfP = ((N / P) * ( 2 * P + (N / P - 1 ) * P)) / 2 ; // Recursively function call to // find the sum for N/P return (sumUptoN + func(N / P, P) - sumOfMultiplesOfP); } // Driver Code public static void main(String[] args) { // Given N and P int N = 10 , P = 5 ; // Function call System.out.println(func(N, P)); } } // This code is contributed by Rajput-Ji |
Python3
# Python3 program for the # above approach # Function to find the sum # of largest divisors of # numbers in range 1 to N # not divisible by prime number P def func(N, P): # Total sum upto N sumUptoN = (N * (N + 1 ) / 2 ); sumOfMultiplesOfP = 0 ; # If no multiple of P exist # up to N if (N < P): return sumUptoN; # If only P itself is # in the range from 1 # to N elif ((N / P) = = 1 ): return sumUptoN - P + 1 ; # Sum of those that are # divisible by P sumOfMultiplesOfP = (((N / P) * ( 2 * P + (N / P - 1 ) * P)) / 2 ); # Recursively function call to # find the sum for N/P return (sumUptoN + func(N / P, P) - sumOfMultiplesOfP); # Driver Code if __name__ = = '__main__' : # Given N and P N = 10 ; P = 5 ; # Function call print (func(N, P)); # This code is contributed by Rajput-Ji |
C#
// C# program for the above approach using System; class GFG{ // Function to find the sum of largest // divisors of numbers in range 1 to N // not divisible by prime number P static int func( int N, int P) { // Total sum upto N int sumUptoN = (N * (N + 1) / 2); int sumOfMultiplesOfP; // If no multiple of P exist up to N if (N < P) { return sumUptoN; } // If only P itself is in the range // from 1 to N else if ((N / P) == 1) { return sumUptoN - P + 1; } // Sum of those that are divisible by P sumOfMultiplesOfP = ((N / P) * (2 * P + (N / P - 1) * P)) / 2; // Recursively function call to // find the sum for N/P return (sumUptoN + func(N / P, P) - sumOfMultiplesOfP); } // Driver Code public static void Main(String[] args) { // Given N and P int N = 10, P = 5; // Function call Console.WriteLine(func(N, P)); } } // This code is contributed by Amit Katiyar |
Javascript
<script> // JavaScript program for the above approach // Function to find the sum of largest // divisors of numbers in range 1 to N // not divisible by prime number P function func(N, P) { // Total sum upto N let sumUptoN = (N * (N + 1) / 2); let sumOfMultiplesOfP; // If no multiple of P exist up to N if (N < P) { return sumUptoN; } // If only P itself is in the range // from 1 to N else if ((N / P) == 1) { return sumUptoN - P + 1; } // Sum of those that are divisible by P sumOfMultiplesOfP = ((N / P) * (2 * P + (N / P - 1) * P)) / 2; // Recursively function call to // find the sum for N/P return (sumUptoN + func(N / P, P) - sumOfMultiplesOfP); } // Driver Code // Given N and P let N = 10, P = 5; // Function call document.write(func(N, P)); </script> |
43
Time Complexity: O(logPN)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!