Ordered Prime Signature | JAVA to find total number of divisors of a number , using ordered prime signature ; Finding primes upto entered number ; Finding primes by Sieve of Eratosthenes method ; If prime [ i ] is not changed , then it is prime ; Update all multiples of p ; Forming array of the prime numbers found ; Finding ordered prime signature of the number ; Map to store prime factors and the related exponents ; Declaring an iterator for map ; Finding prime factorization of the number ; Storing the prime factor and its exponent in map ; Storing the exponent in a vector ; Sorting the stored exponents ; Printing the prime signature ; Finding total number of divisors of the number ; Adding one to each element present ; Multiplying the elements ; Driver code
import java . util . * ; class GFG { static class pair { int first , second ; public pair ( int first , int second ) { this . first = first ; this . second = second ; } } static Vector < Integer > primes ( int n ) { boolean [ ] prime = new boolean [ n + 1 ] ; Arrays . fill ( prime , true ) ; for ( int i = 2 ; i * i <= n ; i ++ ) { if ( prime [ i ] == true ) { for ( int j = i * 2 ; j <= n ; j += i ) prime [ j ] = false ; } } Vector < Integer > arr = new Vector < > ( ) ; for ( int i = 2 ; i <= n ; i ++ ) { if ( prime [ i ] ) arr . add ( i ) ; } return arr ; } static Vector < Integer > signature ( int n ) { Vector < Integer > r = primes ( n ) ; HashMap < Integer , Integer > factor = new HashMap < > ( ) ; HashMap < Integer , Integer > :: iterator it ; Vector < Integer > sort_exp = new Vector < > ( ) ; int k , t = n ; int it = 0 ; for ( int i = 0 ; i < r . size ( ) ; i ++ ) { if ( n % r . get ( i ) == 0 ) { k = 0 ; while ( n % r . get ( i ) == 0 ) { n = n / r . get ( i ) ; k ++ ; } factor . put ( r . get ( i ) , k ) ; sort_exp . add ( k ) ; } } Collections . sort ( sort_exp ) ; System . out . print ( " ▁ The ▁ Ordered ▁ Prime ▁ Signature ▁ of ▁ " + t + " is :  { "); for ( int i = 0 ; i < sort_exp . size ( ) ; i ++ ) { if ( i != sort_exp . size ( ) - 1 ) System . out . print ( sort_exp . get ( i ) + " , ▁ " ) ; else System . out . print ( sort_exp . get ( i ) + " }NEW_LINE"); } return sort_exp ; } static void divisors ( int n ) { int f = 1 , l ; Vector < Integer > div = signature ( n ) ; l = div . size ( ) ; for ( int i = 0 ; i < l ; i ++ ) { f *= ( div . get ( i ) + 1 ) ; } System . out . print ( " The ▁ total ▁ number ▁ of ▁ divisors ▁ of ▁ " + n + " ▁ is ▁ " + f + "NEW_LINE"); } public static void main ( String [ ] args ) { int n = 13 ; divisors ( n ) ; } }