すべての素因数とその累乗を出力します
数値 N を指定すると、その固有の素因数とそのべき乗をすべて N で出力します。
例:
Input: N = 100 Output: Factor Power 2 2 5 2 Input: N = 35 Output: Factor Power 5 1 7 1推奨: で解決してください。 練習する 解決策に進む前に、まず最初に確認してください。
あ シンプルな解決策 まず最初に N の素因数を見つける 。次に、すべての素因数について、N を除算する最大累乗を見つけて出力します。
アン 効率的なソリューション 使うことです エラトステネスのふるい 。
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; } 以下は上記の手順の実装です。
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>
出力：
Factor Power 2 3 3 2 5 1
時間計算量: O(n*log(log(n)))
補助スペース: の上）
上記のアルゴリズムは、s[] を埋めた後、O(Log N) 時間以内にすべてのべき乗を求めます。これは、上限があり、多くのテスト ケースに対して素因数とその累乗を計算する必要がある競争環境では非常に役立ちます。このシナリオでは、配列に s[] を入れる必要があるのは 1 回だけです。
