Java program for Find sum of odd factors of a number
Write a java program for a given number n, the task is to find the odd factor sum.
Examples:
Input: n = 30
Output: 24
Explanation: Odd dividers sum 1 + 3 + 5 + 15 = 24Input: 18
Output: 13
Explanation: Odd dividers sum 1 + 3 + 9 = 13
Java program for Find sum of odd factors of a number using Prime factorization:
To find sum of odd factors, we simply need to ignore even factors and their powers. For example, consider n = 18. It can be written as 2132 and sum of all factors is (1)*(1 + 2)*(1 + 3 + 32). Sum of odd factors (1)*(1+3+32) = 13.
To remove all even factors, we repeatedly divide n while it is divisible by 2. After this step, we only get odd factors. Note that 2 is the only even prime.
Let p1, p2, … pk be prime factors of n. Let a1, a2, .. ak be highest powers of p1, p2, .. pk respectively that divide n, i.e., we can write n as n = (p1a1)*(p2a2)* … (pkak).
Sum of divisors = (1 + p1 + p12 ... p1a1) * (1 + p2 + p22 ... p2a2) * ............................................. (1 + pk + pk2 ... pkak)
Below is the Implementation of the above approach:
Java
// Formula based Java program // to find sum of all divisors // of n. import java.io.*; import java.math.*; class GFG { // Returns sum of all // factors of n. static int sumofoddFactors( int n) { // Traversing through // all prime factors. int res = 1 ; // ignore even factors by // removing all powers // of 2 while (n % 2 == 0 ) n = n / 2 ; for ( int i = 3 ; i <= Math.sqrt(n); i++) { // While i divides n, print i // and divide n int count = 0 , curr_sum = 1 ; int curr_term = 1 ; while (n % i == 0 ) { count++; n = n / i; curr_term *= i; curr_sum += curr_term; } res *= curr_sum; } // This condition is to handle // the case when n is a // prime number. if (n >= 2 ) res *= ( 1 + n); return res; } // Driver code public static void main(String args[]) throws IOException { int n = 30 ; System.out.println(sumofoddFactors(n)); } } /* This code is contributed by Nikita Tiwari.*/ |
Output:
24
Time Complexity: O(sqrt(n))
Auxiliary Space: O(1)
Please refer complete article on Find sum of odd factors of a number for more details!
Contact Us