Imprimer tous les facteurs premiers et leurs puissances
Étant donné un nombre N, imprimez tous ses facteurs premiers uniques et leurs puissances dans N.
Exemples :
Input: N = 100 Output: Factor Power 2 2 5 2 Input: N = 35 Output: Factor Power 5 1 7 1Recommandé : veuillez le résoudre sur ' PRATIQUE ' avant de passer à la solution.
UN Solution simple c'est d'abord trouver les facteurs premiers de N . Ensuite, pour chaque facteur premier, trouvez la puissance la plus élevée qui divise N et imprimez-la.
Un Solution efficace est d'utiliser Tamis d'Ératosthène .
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; } Vous trouverez ci-dessous la mise en œuvre des étapes ci-dessus.
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>
Sortir:
Factor Power 2 3 3 2 5 1
Complexité temporelle : O(n*log(log(n)))
Espace auxiliaire : Sur)
L'algorithme ci-dessus trouve toutes les puissances en un temps O (Log N) après avoir rempli s[]. Cela peut être très utile dans un environnement concurrentiel où nous avons une limite supérieure et où nous devons calculer des facteurs premiers et leurs puissances pour de nombreux cas de test. Dans ce scénario, le tableau ne doit être rempli qu'une seule fois.
