Absolute difference between the count of odd and even factors of N | Java program for the above approach ; Function to find the smallest prime factor of all the numbers using Sieve Of Eratosthenes ; Stores whether any number is prime or not ; Initialize smallest factor as 2 for all the even numbers ; Iterate over the range [ 3 , N ] ; If i is prime ; Iterate all multiples of i ; i is the smallest prime factor of i * j ; Function to find the absolute difference between the count of odd and even factors of N ; Stores the smallest prime factor of i ; Fill values in s [ ] using sieve of eratosthenes ; Stores the total number of factors and the total number of odd and even factors ; Store the current prime factor of the number N ; Store the power of current prime factor ; Loop while N is greater than 1 ; If N also has smallest prime factor as curr , then increment cnt by 1 ; Update only total number of factors if curr is 2 ; Update total number of factors and total number of odd factors ; Update current prime factor as s [ N ] and count as 1 ; Calculate the number of even factors ; Print the difference ; Driver Code
import java . util . * ; class GFG { static void sieveOfEratosthenes ( int N , int s [ ] ) { boolean [ ] prime = new boolean [ N + 1 ] ; for ( int i = 2 ; i <= N ; i += 2 ) s [ i ] = 2 ; for ( int i = 3 ; i <= N ; i += 2 ) { if ( prime [ i ] == false ) { s [ i ] = i ; for ( int j = i ; j * i <= N ; j += 2 ) { if ( ! prime [ i * j ] ) { prime [ i * j ] = true ; s [ i * j ] = i ; } } } } } static void findDifference ( int N ) { int [ ] s = new int [ N + 1 ] ; sieveOfEratosthenes ( N , s ) ; int total = 1 , odd = 1 , even = 0 ; int curr = s [ N ] ; int cnt = 1 ; while ( N > 1 ) { N /= s [ N ] ; if ( curr == s [ N ] ) { cnt ++ ; continue ; } if ( curr == 2 ) { total = total * ( cnt + 1 ) ; } else { total = total * ( cnt + 1 ) ; odd = odd * ( cnt + 1 ) ; } curr = s [ N ] ; cnt = 1 ; } even = total - odd ; System . out . print ( Math . abs ( even - odd ) ) ; } public static void main ( String [ ] args ) { int N = 12 ; findDifference ( N ) ; } }