Dado un entero positivo N , la tarea es encontrar el N número más pequeño en la secuencia que tiene exactamente 4 divisores .
Ejemplos:
Entrada: 4
Salida: 14
Explicación: Los números en la secuencia que tiene 4 divisores son 6, 8, 10, 14,…, el cuarto número en la secuencia es 14.Entrada: 24
Salida: 94
Enfoque: Este problema se puede resolver observando que el número i tiene una descomposición en factores primos de p1 a1 * p2 a2 * p3 a3 …pk ak , entonces el número de divisores de i es (a1+1)(a2+1)…( ak+1). Entonces, para que i tenga exactamente 4 divisores , debe ser igual al producto de dos primos distintos o algún número primo elevado a la potencia 3 . Siga los pasos a continuación para resolver el problema:
- Inicialice los arreglos divs[] y vis[] para almacenar el número de divisores de cualquier número y verificar si el número dado se considera o no, respectivamente.
- Inicialice una variable cnt como 0 para almacenar el número de elementos que tienen exactamente 4 divisores.
- Ahora, usa el algoritmo tamiz de Eratóstenes .
- Iterar mientras cnt es menor que n, usando una variable que empiezo desde 2 :
- Si i es primo :
- Iterar en el rango [2*i, 1000000] usando la variable j con incremento de i :
- Si el número j ya está considerado, entonces continúe .
- Actualice vis[j] como verdadero e inicialice las variables currNum como j y cuente como 0.
- Divida el currNum por i mientras currNum % i es igual a 0, incremente div[j] y cuente por 1.
- Si currNum es igual a 1, count es igual a 3 y divs[j] es igual a 3, luego incremente cnt en 1.
- De lo contrario, si currNum no es igual a 1, count es igual a 1, divs[j] es igual a 1 y divs[currNum] es igual a 0, luego incremente cnt en 1.
- Si cnt es igual a N, imprima j y devuelva .
- Iterar en el rango [2*i, 1000000] usando la variable j con incremento de i :
- Si i es primo :
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the nth number which // has exactly 4 divisors int nthNumber(int n) { // The divs[] array to store number of // divisors of every element int divs[1000000]; // The vis[] array to check if given number // is considered or not bool vis[1000000]; // The cnt stores number of elements having // exactly 4 divisors int cnt = 0; // Iterate while cnt less than n for (int i = 2; cnt < n; i++) { // If i is a prime if (divs[i] == 0) { // Iterate in the range [2*i, 1000000] with // increment of i for (int j = 2 * i; j < 1000000; j += i) { // If the number j is already considered if (vis[j]) { continue; } vis[j] = 1; int currNum = j; int count = 0; // Dividing currNum by i until currNum % i is // equal to 0 while (currNum % i == 0) { divs[j]++; currNum = currNum / i; count++; } // Case a single prime in its factorization if (currNum == 1 && count == 3 && divs[j] == 3) { cnt++; } else if (currNum != 1 && divs[currNum] == 0 && count == 1 && divs[j] == 1) { // Case of two distinct primes which // divides j exactly once each cnt++; } if (cnt == n) { return j; } } } } return -1; } // Driver Code int main() { // Given Input int N = 24; // Function Call cout << nthNumber(N) << endl; return 0; }
Java
// Java program for the above approach import java.io.*; class GFG { // Function to find the nth number which // has exactly 4 divisors static int nthNumber(int n) { // The divs[] array to store number of // divisors of every element int divs[] = new int[1000000]; // The vis[] array to check if given number // is considered or not boolean vis[] = new boolean[1000000]; // The cnt stores number of elements having // exactly 4 divisors int cnt = 0; // Iterate while cnt less than n for (int i = 2; cnt < n; i++) { // If i is a prime if (divs[i] == 0) { // Iterate in the range [2*i, 1000000] with // increment of i for (int j = 2 * i; j < 1000000; j += i) { // If the number j is already considered if (vis[j]) { continue; } vis[j] = true; int currNum = j; int count = 0; // Dividing currNum by i until currNum % // i is equal to 0 while (currNum % i == 0) { divs[j]++; currNum = currNum / i; count++; } // Case a single prime in its // factorization if (currNum == 1 && count == 3 && divs[j] == 3) { cnt++; } else if (currNum != 1 && divs[currNum] == 0 && count == 1 && divs[j] == 1) { // Case of two distinct primes which // divides j exactly once each cnt++; } if (cnt == n) { return j; } } } } return -1; } // Driver Code public static void main(String[] args) { // Given Input int N = 24; // Function Call System.out.println(nthNumber(N)); } } // This code is contributed by Potta Lokesh
Python3
# Python program for the above approach # Function to find the nth number which # has exactly 4 divisors def nthNumber(n): # The divs[] array to store number of # divisors of every element divs = [0 for i in range(1000000)]; # The vis[] array to check if given number # is considered or not vis = [0 for i in range(1000000)]; # The cnt stores number of elements having # exactly 4 divisors cnt = 0; # Iterate while cnt less than n for i in range(2, n): # If i is a prime if (divs[i] == 0): # Iterate in the range [2*i, 1000000] with # increment of i for j in range(2 * i, 1000000): # If the number j is already considered if (vis[j]): continue; vis[j] = 1; currNum = j; count = 0; # Dividing currNum by i until currNum % i is # equal to 0 while (currNum % i == 0): divs[j] += 1; currNum = currNum // i; count += 1; # Case a single prime in its factorization if (currNum == 1 and count == 3 and divs[j] == 3): cnt += 1 elif (currNum != 1 and divs[currNum] == 0 and count == 1 and divs[j] == 1): # Case of two distinct primes which # divides j exactly once each cnt += 1 if (cnt == n): return j; return -1; # Driver Code # Given Input N = 24; # Function Call print(nthNumber(N)); # This code is contributed by gfgking.
C#
// C# program for the above approach using System; // Function to find minimum number of // elements required to obtain sum K class GFG{ // Function to find the nth number which // has exactly 4 divisors static int nthNumber(int n) { // The divs[] array to store number of // divisors of every element int[] divs = new int[1000000]; // The vis[] array to check if given number // is considered or not int[] vis = new int[1000000]; // The cnt stores number of elements having // exactly 4 divisors int cnt = 0; // Iterate while cnt less than n for(int i = 2; cnt < n; i++) { // If i is a prime if (divs[i] == 0) { // Iterate in the range [2*i, 1000000] with // increment of i for(int j = 2 * i; j < 1000000; j += i) { // If the number j is already considered if (vis[j] != 0) { continue; } vis[j] = 1; int currNum = j; int count = 0; // Dividing currNum by i until currNum % i is // equal to 0 while (currNum % i == 0) { divs[j]++; currNum = currNum / i; count++; } // Case a single prime in its factorization if (currNum == 1 && count == 3 && divs[j] == 3) { cnt++; } else if (currNum != 1 && divs[currNum] == 0 && count == 1 && divs[j] == 1) { // Case of two distinct primes which // divides j exactly once each cnt++; } if (cnt == n) { return j; } } } } return -1; } // Driver Code static public void Main () { // Given Input int N = 24; // Function Call Console.Write(nthNumber(N)); } } // This code is contributed by sanjoy_62
Javascript
<script> // JavaScript program for the above approach // Function to find the nth number which // has exactly 4 divisors function nthNumber(n) { // The divs[] array to store number of // divisors of every element let divs = new Array(1000000); for(var i = 0; i < divs.length; i++) { divs[i] = 0; } // The vis[] array to check if given number // is considered or not let vis = new Array(1000000); for(var i = 0; i < vis.length; i++) { vis[i] = 0; } // The cnt stores number of elements having // exactly 4 divisors let cnt = 0; // Iterate while cnt less than n for(let i = 2; cnt < n; i++) { // If i is a prime if (divs[i] == 0) { // Iterate in the range [2*i, 1000000] with // increment of i for(let j = 2 * i; j < 1000000; j += i) { // If the number j is already considered if (vis[j]) { continue; } vis[j] = true; let currNum = j; let count = 0; // Dividing currNum by i until currNum % // i is equal to 0 while (currNum % i == 0) { divs[j]++; currNum = Math.floor(currNum / i); count++; } // Case a single prime in its // factorization if (currNum == 1 && count == 3 && divs[j] == 3) { cnt++; } else if (currNum != 1 && divs[currNum] == 0 && count == 1 && divs[j] == 1) { // Case of two distinct primes which // divides j exactly once each cnt++; } if (cnt == n) { return j; } } } } return -1; } // Driver Code // Given Input let N = 24; // Function Call document.write(nthNumber(N)); // This code is contributed by code_hunt </script>
94
Complejidad de tiempo: O(Nlog(log(N))), donde N es 1000000 .
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por rohitpal210 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA