Imprime todos los factores primos y sus potencias.
Dado un número N, imprima todos sus factores primos únicos y sus potencias en N.
Ejemplos:
Input: N = 100 Output: Factor Power 2 2 5 2 Input: N = 35 Output: Factor Power 5 1 7 1Recomendado: Resuélvelo en ' PRÁCTICA ' primero antes de pasar a la solución.
A Solución sencilla es primero encontrar factores primos de N . Luego, para cada factor primo, encuentre su potencia más alta que divida a N e imprímalo.
Un Solución eficiente es usar Tamiz de Eratóstenes .
1) First compute an array s[N+1] using Sieve of Eratosthenes . s[i] = Smallest prime factor of 'i' that divides 'i'. For example let N = 10 s[2] = s[4] = s[6] = s[8] = s[10] = 2; s[3] = s[9] = 3; s[5] = 5; s[7] = 7; 2) Using the above computed array s[] we can find all powers in O(Log N) time. curr = s[N]; // Current prime factor of N cnt = 1; // Power of current prime factor // Printing prime factors and their powers while (N > 1) { N /= s[N]; // N is now N/s[N]. If new N also has its // smallest prime factor as curr increment // power and continue if (curr == s[N]) { cnt++; continue; } // Print prime factor and its power print (curr cnt); // Update current prime factor as s[N] and // initializing count as 1. curr = s[N]; cnt = 1; } A continuación se muestra la implementación de los pasos anteriores.
C++ // C++ Program to print prime factors and their // powers using Sieve Of Eratosthenes #include using namespace std ; // Using SieveOfEratosthenes to find smallest prime // factor of all the numbers. // For example if N is 10 // s[2] = s[4] = s[6] = s[10] = 2 // s[3] = s[9] = 3 // s[5] = 5 // s[7] = 7 void sieveOfEratosthenes ( int N int s []) { // Create a boolean array 'prime[0..n]' and // initialize all entries in it as false. vector < bool > prime ( N + 1 false ); // Initializing smallest factor equal to 2 // for all the even numbers for ( int i = 2 ; i <= N ; i += 2 ) s [ i ] = 2 ; // For odd numbers less than equal to n for ( int i = 3 ; i <= N ; i += 2 ) { if ( prime [ i ] == false ) { // s(i) for a prime is the number itself s [ i ] = i ; // For all multiples of current prime number for ( int j = i ; j * i <= N ; j += 2 ) { if ( prime [ i * j ] == false ) { prime [ i * j ] = true ; // i is the smallest prime factor for // number 'i*j'. s [ i * j ] = i ; } } } } } // Function to generate prime factors and its power void generatePrimeFactors ( int N ) { // s[i] is going to store smallest prime factor // of i. int s [ N + 1 ]; // Filling values in s[] using sieve sieveOfEratosthenes ( N s ); printf ( 'Factor Power n ' ); int curr = s [ N ]; // Current prime factor of N int cnt = 1 ; // Power of current prime factor // Printing prime factors and their powers while ( N > 1 ) { N /= s [ N ]; // N is now N/s[N]. If new N also has smallest // prime factor as curr increment power if ( curr == s [ N ]) { cnt ++ ; continue ; } printf ( '%d t %d n ' curr cnt ); // Update current prime factor as s[N] and // initializing count as 1. curr = s [ N ]; cnt = 1 ; } } //Driver Program int main () { int N = 360 ; generatePrimeFactors ( N ); return 0 ; }
Java // Java Program to print prime // factors and their powers using // Sieve Of Eratosthenes import java.io.* ; public class GFG { // Using SieveOfEratosthenes // to find smallest prime // factor of all the numbers. // For example if N is 10 // s[2] = s[4] = s[6] = s[10] = 2 // s[3] = s[9] = 3 // s[5] = 5 // s[7] = 7 static void sieveOfEratosthenes ( int N int s [] ) { // Create a boolean array // 'prime[0..n]' and initialize // all entries in it as false. boolean [] prime = new boolean [ N + 1 ] ; // Initializing smallest // factor equal to 2 // for all the even numbers for ( int i = 2 ; i <= N ; i += 2 ) s [ i ] = 2 ; // For odd numbers less // then equal to n for ( int i = 3 ; i <= N ; i += 2 ) { if ( prime [ i ] == false ) { // s(i) for a prime is // the number itself s [ i ] = i ; // For all multiples of // current prime number for ( int j = i ; j * i <= N ; j += 2 ) { if ( prime [ i * j ] == false ) { prime [ i * j ] = true ; // i is the smallest prime // factor for number 'i*j'. s [ i * j ] = i ; } } } } } // Function to generate prime // factors and its power static void generatePrimeFactors ( int N ) { // s[i] is going to store // smallest prime factor of i. int [] s = new int [ N + 1 ] ; // Filling values in s[] using sieve sieveOfEratosthenes ( N s ); System . out . println ( 'Factor Power' ); int curr = s [ N ] ; // Current prime factor of N int cnt = 1 ; // Power of current prime factor // Printing prime factors // and their powers while ( N > 1 ) { N /= s [ N ] ; // N is now N/s[N]. If new N // also has smallest prime // factor as curr increment power if ( curr == s [ N ] ) { cnt ++ ; continue ; } System . out . println ( curr + 't' + cnt ); // Update current prime factor // as s[N] and initializing // count as 1. curr = s [ N ] ; cnt = 1 ; } } // Driver Code public static void main ( String [] args ) { int N = 360 ; generatePrimeFactors ( N ); } } // This code is contributed by mits
Python3 # Python3 program to print prime # factors and their powers # using Sieve Of Eratosthenes # Using SieveOfEratosthenes to # find smallest prime factor # of all the numbers. # For example if N is 10 # s[2] = s[4] = s[6] = s[10] = 2 # s[3] = s[9] = 3 # s[5] = 5 # s[7] = 7 def sieveOfEratosthenes ( N s ): # Create a boolean array # 'prime[0..n]' and initialize # all entries in it as false. prime = [ False ] * ( N + 1 ) # Initializing smallest factor # equal to 2 for all the even # numbers for i in range ( 2 N + 1 2 ): s [ i ] = 2 # For odd numbers less than # equal to n for i in range ( 3 N + 1 2 ): if ( prime [ i ] == False ): # s(i) for a prime is # the number itself s [ i ] = i # For all multiples of # current prime number for j in range ( i int ( N / i ) + 1 2 ): if ( prime [ i * j ] == False ): prime [ i * j ] = True # i is the smallest # prime factor for # number 'i*j'. s [ i * j ] = i # Function to generate prime # factors and its power def generatePrimeFactors ( N ): # s[i] is going to store # smallest prime factor # of i. s = [ 0 ] * ( N + 1 ) # Filling values in s[] # using sieve sieveOfEratosthenes ( N s ) print ( 'Factor Power' ) # Current prime factor of N curr = s [ N ] # Power of current prime factor cnt = 1 # Printing prime factors and #their powers while ( N > 1 ): N //= s [ N ] # N is now N/s[N]. If new N # also has smallest prime # factor as curr increment # power if ( curr == s [ N ]): cnt += 1 continue print ( str ( curr ) + ' t ' + str ( cnt )) # Update current prime factor # as s[N] and initializing # count as 1. curr = s [ N ] cnt = 1 #Driver Program N = 360 generatePrimeFactors ( N ) # This code is contributed by Ansu Kumari
C# // C# Program to print prime // factors and their powers using // Sieve Of Eratosthenes class GFG { // Using SieveOfEratosthenes // to find smallest prime // factor of all the numbers. // For example if N is 10 // s[2] = s[4] = s[6] = s[10] = 2 // s[3] = s[9] = 3 // s[5] = 5 // s[7] = 7 static void sieveOfEratosthenes ( int N int [] s ) { // Create a boolean array // 'prime[0..n]' and initialize // all entries in it as false. bool [] prime = new bool [ N + 1 ]; // Initializing smallest // factor equal to 2 // for all the even numbers for ( int i = 2 ; i <= N ; i += 2 ) s [ i ] = 2 ; // For odd numbers less // then equal to n for ( int i = 3 ; i <= N ; i += 2 ) { if ( prime [ i ] == false ) { // s(i) for a prime is // the number itself s [ i ] = i ; // For all multiples of // current prime number for ( int j = i ; j * i <= N ; j += 2 ) { if ( prime [ i * j ] == false ) { prime [ i * j ] = true ; // i is the smallest prime // factor for number 'i*j'. s [ i * j ] = i ; } } } } } // Function to generate prime // factors and its power static void generatePrimeFactors ( int N ) { // s[i] is going to store // smallest prime factor of i. int [] s = new int [ N + 1 ]; // Filling values in s[] using sieve sieveOfEratosthenes ( N s ); System . Console . WriteLine ( 'Factor Power' ); int curr = s [ N ]; // Current prime factor of N int cnt = 1 ; // Power of current prime factor // Printing prime factors // and their powers while ( N > 1 ) { N /= s [ N ]; // N is now N/s[N]. If new N // also has smallest prime // factor as curr increment power if ( curr == s [ N ]) { cnt ++ ; continue ; } System . Console . WriteLine ( curr + 't' + cnt ); // Update current prime factor // as s[N] and initializing // count as 1. curr = s [ N ]; cnt = 1 ; } } // Driver Code static void Main () { int N = 360 ; generatePrimeFactors ( N ); } } // This code is contributed by mits
PHP // PHP Program to print prime factors and // their powers using Sieve Of Eratosthenes // Using SieveOfEratosthenes to find smallest // prime factor of all the numbers. // For example if N is 10 // s[2] = s[4] = s[6] = s[10] = 2 // s[3] = s[9] = 3 // s[5] = 5 // s[7] = 7 function sieveOfEratosthenes ( $N & $s ) { // Create a boolean array 'prime[0..n]' and // initialize all entries in it as false. $prime = array_fill ( 0 $N + 1 false ); // Initializing smallest factor equal // to 2 for all the even numbers for ( $i = 2 ; $i <= $N ; $i += 2 ) $s [ $i ] = 2 ; // For odd numbers less than equal to n for ( $i = 3 ; $i <= $N ; $i += 2 ) { if ( $prime [ $i ] == false ) { // s(i) for a prime is the // number itself $s [ $i ] = $i ; // For all multiples of current // prime number for ( $j = $i ; $j * $i <= $N ; $j += 2 ) { if ( $prime [ $i * $j ] == false ) { $prime [ $i * $j ] = true ; // i is the smallest prime factor // for number 'i*j'. $s [ $i * $j ] = $i ; } } } } } // Function to generate prime factors // and its power function generatePrimeFactors ( $N ) { // s[i] is going to store smallest // prime factor of i. $s = array_fill ( 0 $N + 1 0 ); // Filling values in s[] using sieve sieveOfEratosthenes ( $N $s ); print ( 'Factor Power n ' ); $curr = $s [ $N ]; // Current prime factor of N $cnt = 1 ; // Power of current prime factor // Printing prime factors and their powers while ( $N > 1 ) { if ( $s [ $N ]) $N = ( int )( $N / $s [ $N ]); // N is now N/s[N]. If new N als has smallest // prime factor as curr increment power if ( $curr == $s [ $N ]) { $cnt ++ ; continue ; } print ( $curr . ' t ' . $cnt . ' n ' ); // Update current prime factor as s[N] // and initializing count as 1. $curr = $s [ $N ]; $cnt = 1 ; } } // Driver Code $N = 360 ; generatePrimeFactors ( $N ); // This code is contributed by mits ?>
JavaScript < script > // javascript Program to print prime // factors and their powers using // Sieve Of Eratosthenes // Using SieveOfEratosthenes // to find smallest prime // factor of all the numbers. // For example if N is 10 // s[2] = s[4] = s[6] = s[10] = 2 // s[3] = s[9] = 3 // s[5] = 5 // s[7] = 7 function sieveOfEratosthenes ( N s ) { // Create a boolean array // 'prime[0..n]' and initialize // all entries in it as false. prime = Array . from ({ length : N + 1 } ( _ i ) => false ); // Initializing smallest // factor equal to 2 // for all the even numbers for ( i = 2 ; i <= N ; i += 2 ) s [ i ] = 2 ; // For odd numbers less // then equal to n for ( i = 3 ; i <= N ; i += 2 ) { if ( prime [ i ] == false ) { // s(i) for a prime is // the number itself s [ i ] = i ; // For all multiples of // current prime number for ( j = i ; j * i <= N ; j += 2 ) { if ( prime [ i * j ] == false ) { prime [ i * j ] = true ; // i is the smallest prime // factor for number 'i*j'. s [ i * j ] = i ; } } } } } // Function to generate prime // factors and its power function generatePrimeFactors ( N ) { // s[i] is going to store // smallest prime factor of i. var s = Array . from ({ length : N + 1 } ( _ i ) => 0 ); // Filling values in s using sieve sieveOfEratosthenes ( N s ); document . write ( 'Factor Power' ); var curr = s [ N ]; // Current prime factor of N var cnt = 1 ; // Power of current prime factor // Printing prime factors // and their powers while ( N > 1 ) { N /= s [ N ]; // N is now N/s[N]. If new N // also has smallest prime // factor as curr increment power if ( curr == s [ N ]) { cnt ++ ; continue ; } document . write ( '
' + curr + 't' + cnt ); // Update current prime factor // as s[N] and initializing // count as 1. curr = s [ N ]; cnt = 1 ; } } // Driver Code var N = 360 ; generatePrimeFactors ( N ); // This code contributed by Princi Singh < /script>
Producción:
Factor Power 2 3 3 2 5 1
Complejidad del tiempo: O(n*log(log(n)))
Espacio Auxiliar: En)
El algoritmo anterior encuentra todas las potencias en el tiempo O(Log N) después de haber llenado s[]. Esto puede resultar muy útil en un entorno competitivo donde tenemos un límite superior y necesitamos calcular factores primos y sus potencias para muchos casos de prueba. En este escenario, la matriz debe llenarse s[] solo una vez.
