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 Pint 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 Codeint 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 approachimport 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 Pstatic 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 Codepublic 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 Pdef 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 Codeif __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 approachusing System;class GFG{// Function to find the sum of largest// divisors of numbers in range 1 to N// not divisible by prime number Pstatic 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 Codepublic 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 Pfunction 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!
