Donat un nombre N, imprimiu tots els seus factors primers únics i les seves potències en N.
Exemples:
Input: N = 100 Output: Factor Power 2 2 5 2 Input: N = 35 Output: Factor Power 5 1 7 1Recomanat: si us plau, resol-ho a ' PRÀCTICA primer abans de passar a la solució.
A Solució senzilla és el primer Trobeu els factors primers de N . Aleshores, per a cada factor primer, trobeu la potència més alta del mateix que divideix N i imprimiu-lo.
An Solució eficient és utilitzar Sedós d'Eratostenes .
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ó es mostra la implementació dels passos anteriors.
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>
Sortida:
Factor Power 2 3 3 2 5 1
Complexitat temporal: O(n*log(log(n)))
Espai auxiliar: O(n)
L'algorisme anterior troba totes les potències en temps O(Log N) després d'haver omplert s[]. Això pot ser molt útil en un entorn competitiu on tenim un límit superior i necessitem calcular factors primers i les seves potències per a molts casos de prova. En aquest escenari, la matriu només s'ha d'omplir una vegada.
món Wumpus