Dado un número entero N . La tarea es encontrar el número de divisores de todos los números en el rango [1, N] .
Ejemplos:
Entrada: N = 5
Salida: 1 2 2 3 2
divisores(1) = 1
divisores(2) = 1 y 2
divisores(3) = 1 y 3
divisores(4) = 1, 2 y 4
divisores(5) = 1 y 5Entrada: N = 10
Salida: 1 2 2 3 2 4 2 4 3 4
Enfoque: Cree una array arr[] del tamaño (N + 1) donde arr[i] almacena la cantidad de divisores de i . Ahora, para cada j del rango [1, N] , incremente todos los elementos que son divisibles por j .
Por ejemplo, si j = 3 , actualice arr[3], arr[6], arr[9], …
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to find the number of divisors // of all numbers in the range [1, n] void findDivisors(int n) { // Array to store the count // of divisors int div[n + 1]; memset(div, 0, sizeof div); // For every number from 1 to n for (int i = 1; i <= n; i++) { // Increase divisors count for // every number divisible by i for (int j = 1; j * i <= n; j++) div[i * j]++; } // Print the divisors for (int i = 1; i <= n; i++) cout << div[i] << " "; } // Driver code int main() { int n = 10; findDivisors(n); return 0; }
Java
// Java implementation of the approach class GFG { // Function to find the number of divisors // of all numbers in the range [1, n] static void findDivisors(int n) { // Array to store the count // of divisors int[] div = new int[n + 1]; // For every number from 1 to n for (int i = 1; i <= n; i++) { // Increase divisors count for // every number divisible by i for (int j = 1; j * i <= n; j++) div[i * j]++; } // Print the divisors for (int i = 1; i <= n; i++) System.out.print(div[i]+" "); } // Driver code public static void main(String args[]) { int n = 10; findDivisors(n); } } // This code is contributed by Ryuga
Python3
# Python3 implementation of the approach # Function to find the number of divisors # of all numbers in the range [1,n] def findDivisors(n): # List to store the count # of divisors div = [0 for i in range(n + 1)] # For every number from 1 to n for i in range(1, n + 1): # Increase divisors count for # every number divisible by i for j in range(1, n + 1): if j * i <= n: div[i * j] += 1 # Print the divisors for i in range(1, n + 1): print(div[i], end = " ") # Driver Code if __name__ == "__main__": n = 10 findDivisors(n) # This code is contributed by # Vivek Kumar Singh
C#
// C# implementation of the approach using System; class GFG { // Function to find the number of divisors // of all numbers in the range [1, n] static void findDivisors(int n) { // Array to store the count // of divisors int[] div = new int[n + 1]; // For every number from 1 to n for (int i = 1; i <= n; i++) { // Increase divisors count for // every number divisible by i for (int j = 1; j * i <= n; j++) div[i * j]++; } // Print the divisors for (int i = 1; i <= n; i++) Console.Write(div[i]+" "); } // Driver code static void Main() { int n = 10; findDivisors(n); } } // This code is contributed by mits
PHP
<?php // PHP implementation of the approach // Function to find the number of divisors // of all numbers in the range [1, n] function findDivisors($n) { // Array to store the count // of divisors $div = array_fill(0, $n + 2, 0); // For every number from 1 to n for ($i = 1; $i <= $n; $i++) { // Increase divisors count for // every number divisible by i for ($j = 1; $j * $i <= $n; $j++) $div[$i * $j]++; } // Print the divisors for ($i = 1; $i <= $n; $i++) echo $div[$i], " "; } // Driver code $n = 10; findDivisors($n); // This code is contributed // by Arnab Kundu ?>
Javascript
<script> // Javascript implementation of the approach // Function to find the number of divisors // of all numbers in the range [1, n] function findDivisors(n) { // Array to store the count // of divisors let div = new Array(n + 1).fill(0); // For every number from 1 to n for(let i = 1; i <= n; i++) { // Increase divisors count for // every number divisible by i for(let j = 1; j * i <= n; j++) div[i * j]++; } // Print the divisors for(let i = 1; i <= n; i++) document.write(div[i] + " "); } // Driver code let n = 10; findDivisors(n); // This code is contributed by souravmahato348 </script>
1 2 2 3 2 4 2 4 3 4
Complejidad de Tiempo: O(n 3/2 )
Espacio Auxiliar: O(n)
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA