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>
Producción
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