Geben Sie bei einer gegebenen Zahl N alle ihre eindeutigen Primfaktoren und ihre Potenzen in N an.
Beispiele:
Input: N = 100 Output: Factor Power 2 2 5 2 Input: N = 35 Output: Factor Power 5 1 7 1Empfohlen: Bitte lösen Sie es auf ' ÜBEN ' zuerst, bevor wir zur Lösung übergehen.
A Einfache Lösung ist zuerst Finden Sie Primfaktoren von N . Finden Sie dann für jeden Primfaktor dessen höchste Potenz, die N teilt, und drucken Sie sie aus.
Ein Effiziente Lösung ist zu verwenden Sieb des Eratosthenes .
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; } Nachfolgend finden Sie die Umsetzung der oben genannten Schritte.
C++// C++ Program to print prime factors and their // powers using Sieve Of Eratosthenes #include
// 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 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# 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 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 Powern'); $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 ?> <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>
Ausgabe:
Factor Power 2 3 3 2 5 1
Zeitkomplexität: O(n*log(log(n)))
Hilfsraum: An)
Der obige Algorithmus findet alle Potenzen in O(Log N) Zeit, nachdem wir s[] gefüllt haben. Dies kann in einem Wettbewerbsumfeld sehr nützlich sein, in dem wir eine Obergrenze haben und für viele Testfälle Primfaktoren und ihre Potenzen berechnen müssen. In diesem Szenario muss das Array nur einmal mit s[] gefüllt werden.
Angular CLI deinstallieren