Ordered Prime Signature | CPP 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 ; in ordered prime signature ; Multiplying the elements ; Driver Method
#include <bits/stdc++.h> NEW_LINE using namespace std ; vector < int > primes ( int n ) { bool prime [ n + 1 ] ; memset ( prime , true , sizeof ( prime ) ) ; 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 < int > arr ; for ( int i = 2 ; i <= n ; i ++ ) { if ( prime [ i ] ) arr . push_back ( i ) ; } return arr ; } vector < int > signature ( int n ) { vector < int > r = primes ( n ) ; map < int , int > factor ; map < int , int > :: iterator it ; vector < int > sort_exp ; int k , t = n ; it = factor . begin ( ) ; for ( int i = 0 ; i < r . size ( ) ; i ++ ) { if ( n % r [ i ] == 0 ) { k = 0 ; while ( n % r [ i ] == 0 ) { n = n / r [ i ] ; k ++ ; } factor . insert ( it , pair < int , int > ( r [ i ] , k ) ) ; sort_exp . push_back ( k ) ; } } sort ( sort_exp . begin ( ) , sort_exp . end ( ) ) ; cout << " ▁ The ▁ Ordered ▁ Prime ▁ Signature ▁ of ▁ " << t << " ▁ is ▁ : ▁ STRNEWLINE { ▁ " ; for ( int i = 0 ; i < sort_exp . size ( ) ; i ++ ) { if ( i != sort_exp . size ( ) - 1 ) cout << sort_exp [ i ] << " , ▁ " ; else cout << sort_exp [ i ] << " ▁ } STRNEWLINE " ; } return sort_exp ; } void divisors ( int n ) { int f = 1 , l ; vector < int > div = signature ( n ) ; l = div . size ( ) ; for ( int i = 0 ; i < l ; i ++ ) { div [ i ] += 1 ; f *= div [ i ] ; } cout << " The ▁ total ▁ number ▁ of ▁ divisors ▁ of ▁ " << n << " ▁ is ▁ " << f << " STRNEWLINE " ; } int main ( ) { int n = 13 ; divisors ( n ) ; return 0 ; }