Número gratuito de Nth Square

Dado un número n, encuentre el n-ésimo número libre de cuadrados. Un número no tiene cuadrados si no es divisible por un cuadrado perfecto distinto de 1.
Ejemplos: 
 

Input : n = 2
Output : 2

Input : 5
Output : 6
There is one number (in range from 1 to 6) 
that is divisible by a square. The number
is 4.

Método 1 (Fuerza bruta): 
la idea es verificar iterativamente cada número si es divisible por cualquier número cuadrado perfecto y aumentar el conteo cada vez que se encuentre un número libre de cuadrados y devolver el número libre de cuadrados enésimo.
A continuación se muestra la implementación:
 

C++

// Program to find the nth square free number
#include<bits/stdc++.h>
using namespace std;
 
// Function to find nth square free number
int squareFree(int n)
{
    // To maintain count of square free number
    int cnt = 0;
 
    // Loop for square free numbers
    for (int i=1;; i++)
    {
        bool isSqFree = true;
        for (int j=2; j*j<=i; j++)
        {
            // Checking whether square of a number
            // is divisible by any number which is
            // a perfect square
            if (i % (j*j) == 0)
            {
                isSqFree = false;
                break;
            }
        }
 
        // If number is square free
        if (isSqFree == true)
        {
           cnt++;
 
           // If the cnt becomes n, return
           // the number
           if (cnt == n)
              return i;
        }
    }
    return 0;
}
 
// Driver Program
int main()
{
    int n = 10;
    cout << squareFree(n) << endl;
    return 0;
}

Java

// Java Program to find the nth square
// free number
import java.io.*;
 
class GFG {
     
    // Function to find nth square free
    // number
    public static int squareFree(int n)
    {
         
        // To maintain count of square
        // free number
        int cnt = 0;
     
        // Loop for square free numbers
        for (int i = 1; ; i++) {
             
            boolean isSqFree = true;
             
            for (int j = 2; j * j <= i; j++)
            {
                 
                // Checking whether square
                // of a number is divisible
                // by any number which is
                // a perfect square
                if (i % (j * j) == 0) {
                    isSqFree = false;
                    break;
                }
            }
         
            // If number is square free
            if (isSqFree == true) {
                cnt++;
         
                // If the cnt becomes n,
                // return the number
                if (cnt == n)
                    return i;
            }
        }
    }
     
    // driven code
    public static void main(String[] args) {
         
        int n = 10;
         
        System.out.println("" + squareFree(n));
    }
}
 
// This code is contributed by sunnysingh

Python3

# Python3 Program to find the nth
# square free number
 
# Function to find nth square
# free number
def squareFree(n):
     
    # To maintain count of
    # square free number
    cnt = 0;
 
    # Loop for square free numbers
    i = 1;
    while (True):
        isSqFree = True;
        j = 2;
        while (j * j <= i):
             
            # Checking whether square of a number
            # is divisible by any number which is
            # a perfect square
            if (i % (j * j) == 0):
                isSqFree = False;
                break;
            j += 1;
 
        # If number is square free
        if (isSqFree == True):
            cnt += 1;
     
            # If the cnt becomes n, return the number
            if (cnt == n):
                return i;
        i += 1;
 
    return 0;
 
# Driver Code
n = 10;
print(squareFree(n));
 
# This code is contributed by mits

C#

// C# Program to find the
// nth square free number
using System;
 
class GFG {
     
    // Function to find nth
    // square free number
    public static int squareFree(int n)
    {
        // To maintain count of
        // square free number
        int cnt = 0;
     
        // Loop for square free numbers
        for (int i = 1; ; i++)
        {
            bool isSqFree = true;
             
            for (int j = 2; j * j <= i; j++)
            {
                // Checking whether square
                // of a number is divisible
                // by any number which is
                // a perfect square
                if (i % (j * j) == 0) {
                    isSqFree = false;
                    break;
                }
            }
         
            // If number is square free
            if (isSqFree == true) {
                cnt++;
         
                // If the cnt becomes n,
                // return the number
                if (cnt == n)
                    return i;
            }
        }
    }
     
    // Driver code
    public static void Main()
    {
        int n = 10;
        Console.Write("" + squareFree(n));
    }
}
 
// This code is contributed by nitin mittal

PHP

<?php
// PHP Program to find the
// nth square free number
 
// Function to find nth
// square free number
function squareFree($n)
{
     
    // To maintain count of
    // square free number
    $cnt = 0;
 
    // Loop for square
    // free numbers
    for ($i = 1; ; $i++)
    {
        $isSqFree = true;
        for ($j = 2; $j * $j <= $i; $j++)
        {
             
            // Checking whether square of a number
            // is divisible by any number which is
            // a perfect square
            if ($i % ($j * $j) == 0)
            {
                $isSqFree = false;
                break;
            }
        }
 
        // If number is square free
        if ($isSqFree == true)
        {
            $cnt++;
     
            // If the cnt becomes n,
            // return the number
            if ($cnt == $n)
                return $i;
        }
    }
    return 0;
}
 
// Driver Code
$n = 10;
echo(squareFree($n));
 
// This code is contributed by Ajit.
?>

Javascript

<script>
 
// JavaScript program for the above approach
 
    // Function to find nth square free
    // number
    function squareFree(n)
    {
         
        // To maintain count of square
        // free number
        let cnt = 0;
     
        // Loop for square free numbers
        for (let i = 1; ; i++) {
             
            let isSqFree = true;
             
            for (let j = 2; j * j <= i; j++)
            {
                 
                // Checking whether square
                // of a number is divisible
                // by any number which is
                // a perfect square
                if (i % (j * j) == 0) {
                    isSqFree = false;
                    break;
                }
            }
         
            // If number is square free
            if (isSqFree == true) {
                cnt++;
         
                // If the cnt becomes n,
                // return the number
                if (cnt == n)
                    return i;
            }
        }
    }
 
// Driver Code
    let n = 10;
    document.write("" + squareFree(n));
 
// This code is contributed by susmitakundugoaldanga.
</script>

Producción:  

14

Método 2 (mejor enfoque): 
la idea es contar números libres de cuadrados menores o iguales al límite superior ‘k’ y luego aplicar la búsqueda binaria para encontrar el número libre de cuadrados n. Primero, calculamos el conteo de números cuadrados (números con cuadrados como factores) hasta ‘k’ y luego restamos ese conteo de los números totales para obtener el conteo de números libres de cuadrados hasta ‘k’.
Explicación: 
 

  1. Si cualquier número entero tiene un cuadrado perfecto como factor, entonces se garantiza que también tiene un cuadrado primo como factor. Entonces necesitamos contar los números enteros menores o iguales a ‘k’ que tienen el cuadrado de los números primos como factor. 
    Por ejemplo, encuentre el número de enteros que tienen 4 o 9 como factor hasta ‘k’. Se puede hacer usando el principio de inclusión-exclusión . Usando el principio de inclusión-exclusión , el número total de enteros es [k/4] + [k/9] -[k/36] donde [] es la función entera más grande.
  2. Aplique recursivamente la inclusión y la exclusión hasta que el valor del entero más grande sea cero. Este paso devolverá el conteo de números con cuadrados como factores.
  3. Aplique la búsqueda binaria para encontrar el enésimo número libre de cuadrados.

A continuación se muestra la implementación del algoritmo anterior: 
 

C++

// Program to find the nth square free number
#include<bits/stdc++.h>
using namespace std;
 
// Maximum prime number to be considered for square
// divisibility
const int MAX_PRIME = 100000;
 
// Maximum value of result. We do binary search from 1
// to MAX_RES
const int MAX_RES = 2000000000l;
 
void SieveOfEratosthenes(vector<long long> &a)
{
    // Create a boolean array "prime[0..n]" and initialize
    // all entries it as true. A value in prime[i] will
    // finally be false if i is Not a prime, else true.
    bool prime[MAX_PRIME + 1];
    memset(prime, true, sizeof(prime));
 
    for (long long p=2; p*p<=MAX_PRIME; p++)
    {
        // If prime[p] is not changed, then it is a prime
        if (prime[p] == true)
        {
            // Update all multiples of p
            for (long long i=p*2; i<=MAX_PRIME; i += p)
                prime[i] = false;
        }
    }
 
    // Store all prime numbers in a[]
    for (long long p=2; p<=MAX_PRIME; p++)
        if (prime[p])
            a.push_back(p);
}
 
// Function to count integers upto k which are having
// perfect squares as factors. i is index of next
// prime number whose square needs to be checked.
// curr is current number whose square to be checked.
long long countSquares(long long i, long long cur,
                       long long k, vector<long long> &a)
{
    // variable to store square of prime
    long long square = a[i]*a[i];
 
    long long newCur = square*cur;
 
    // If value of greatest integer becomes zero
    if (newCur > k)
        return 0;
 
    // Applying inclusion-exclusion principle
 
    // Counting integers with squares as factor
    long long cnt = k/(newCur);
 
    // Inclusion (Recur for next prime number)
    cnt += countSquares(i+1, cur, k, a);
 
    // Exclusion (Recur for next prime number)
    cnt -= countSquares(i+1, newCur, k, a);
 
    // Final count
    return cnt;
}
 
// Function to return nth square free number
long long squareFree(long long n)
{
    // Computing primes and storing it in an array a[]
    vector <long long> a;
    SieveOfEratosthenes(a);
 
    // Applying binary search
    long long low = 1;
    long long high = MAX_RES;
 
    while (low < high)
    {
        long long mid = low + (high - low)/2;
 
        // 'c' contains Number of square free numbers
        // less than or equal to 'mid'
        long long c = mid - countSquares(0, 1, mid, a);
 
        // If c < n, then search right side of mid
        // else search left side of mid
        if (c < n)
            low = mid+1;
        else
            high = mid;
    }
 
    // nth square free number
    return low;
}
 
// Driver Program
int main()
{
    int n = 10;
    cout << squareFree(n) << endl;
    return 0;
}

Java

// Java Program to find the nth square free number
import java.util.*;
 
class GFG
{
 
// Maximum prime number to be considered for square
// divisibility
static int MAX_PRIME = 100000;
 
// Maximum value of result. We do
// binary search from 1 to MAX_RES
static int MAX_RES = 2000000000;
 
static void SieveOfEratosthenes(Vector<Long> a)
{
    // Create a boolean array "prime[0..n]"
    // and initialize all entries it as
    // true. A value in prime[i] will
    // finally be false if i is Not
    // a prime, else true.
    boolean prime[] = new boolean[MAX_PRIME + 1];
    Arrays.fill(prime, true);
 
    for (int p = 2; p * p <= MAX_PRIME; p++)
    {
        // If prime[p] is not changed,
        // then it is a prime
        if (prime[p] == true)
        {
            // Update all multiples of p
            for (int i = p * 2; i <= MAX_PRIME; i += p)
                prime[i] = false;
        }
    }
 
    // Store all prime numbers in a[]
    for (int p = 2; p <= MAX_PRIME; p++)
        if (prime[p])
            a.add((long)p);
}
 
// Function to count integers upto k which are having
// perfect squares as factors. i is index of next
// prime number whose square needs to be checked.
// curr is current number whose square to be checked.
static long countSquares(long i, long cur,
                    long k, Vector<Long> a)
{
    // variable to store square of prime
    long square = a.get((int) i)*a.get((int)(i));
 
    long newCur = square*cur;
 
    // If value of greatest integer becomes zero
    if (newCur > k)
        return 0;
 
    // Applying inclusion-exclusion principle
 
    // Counting integers with squares as factor
    long cnt = k/(newCur);
 
    // Inclusion (Recur for next prime number)
    cnt += countSquares(i + 1, cur, k, a);
 
    // Exclusion (Recur for next prime number)
    cnt -= countSquares(i + 1, newCur, k, a);
 
    // Final count
    return cnt;
}
 
// Function to return nth square free number
static long squareFree(long n)
{
    // Computing primes and storing it in an array a[]
    Vector <Long> a = new Vector<>();
    SieveOfEratosthenes(a);
 
    // Applying binary search
    long low = 1;
    long high = MAX_RES;
 
    while (low < high)
    {
        long mid = low + (high - low)/2;
 
        // 'c' contains Number of square free numbers
        // less than or equal to 'mid'
        long c = mid - countSquares(0, 1, mid, a);
 
        // If c < n, then search right side of mid
        // else search left side of mid
        if (c < n)
            low = mid+1;
        else
            high = mid;
    }
 
    // nth square free number
    return low;
}
 
// Driver code
public static void main(String[] args)
{
    int n = 10;
    System.out.println(squareFree(n));
}
}
 
// This code has been contributed by 29AjayKumar

Python3

# Python 3 Program to find the nth square free number
import sys
sys.setrecursionlimit(15000)
 
# Maximum prime number to be considered for square
# divisibility
MAX_PRIME = 100000;
 
# Maximum value of result. We do binary search from 1
# to MAX_RES
MAX_RES = 2000000000
 
def SieveOfEratosthenes(a):
 
    # Create a boolean array "prime[0..n]" and initialize
    # all entries it as true. A value in prime[i] will
    # finally be false if i is Not a prime, else true.
    prime = [True for i in range(MAX_PRIME + 1)];
    p = 2
 
    while(p * p <= MAX_PRIME):
         
        # If prime[p] is not changed, then it is a prime
        if (prime[p] == True):
         
            # Update all multiples of p
            for i in range(p * 2, MAX_PRIME + 1, p):           
                prime[i] = False;
        p += 1
         
    # Store all prime numbers in a[]
    for p in range(2, MAX_PRIME + 1):  
        if (prime[p]):
            a.append(p);   
    return a
 
# Function to count integers upto k which are having
# perfect squares as factors. i is index of next
# prime number whose square needs to be checked.
# curr is current number whose square to be checked.
def countSquares(i, cur, k, a):
 
    # variable to store square of prime
    square = a[i]*a[i];
    newCur = square*cur;
 
    # If value of greatest integer becomes zero
    if (newCur > k):
        return 0, a;
 
    # Applying inclusion-exclusion principle
 
    # Counting integers with squares as factor
    cnt = k//(newCur);
 
    # Inclusion (Recur for next prime number)
    tmp, a = countSquares(i + 1, cur, k, a);
 
    cnt += tmp
     
    # Exclusion (Recur for next prime number)
    tmp, a = countSquares(i + 1, newCur, k, a);
    cnt -= tmp
     
    # Final count
    return cnt,a;
 
# Function to return nth square free number
def squareFree(n):
 
    # Computing primes and storing it in an array a[]
    a = SieveOfEratosthenes([]);
 
    # Applying binary search
    low = 1;
    high = MAX_RES;
    while (low < high): 
        mid = low + (high - low)//2;
 
        # 'c' contains Number of square free numbers
        # less than or equal to 'mid'
        c,a = countSquares(0, 1, mid, a);
        c = mid - c
 
        # If c < n, then search right side of mid
        # else search left side of mid
        if (c < n):
            low = mid + 1;
        else:
            high = mid;
     
    # nth square free number
    return low;
 
# Driver Program
if __name__=='__main__':
 
    n = 10;
    print(squareFree(n))
     
# This code is contributed by rohitsingh07052.

C#

// C# Program to find the nth square free number
using System;
using System.Collections.Generic;
 
class GFG
{
 
// Maximum prime number to be considered
// for square divisibility
static int MAX_PRIME = 100000;
 
// Maximum value of result. We do
// binary search from 1 to MAX_RES
static int MAX_RES = 2000000000;
 
static void SieveOfEratosthenes(List<long> a)
{
    // Create a boolean array "prime[0..n]"
    // and initialize all entries it as
    // true. A value in prime[i] will
    // finally be false if i is Not
    // a prime, else true.
    bool []prime = new bool[MAX_PRIME + 1];
    for(int i = 0; i < MAX_PRIME + 1; i++)
        prime[i] = true;
 
    for (int p = 2; p * p <= MAX_PRIME; p++)
    {
        // If prime[p] is not changed,
        // then it is a prime
        if (prime[p] == true)
        {
            // Update all multiples of p
            for (int i = p * 2; i <= MAX_PRIME; i += p)
                prime[i] = false;
        }
    }
 
    // Store all prime numbers in a[]
    for (int p = 2; p <= MAX_PRIME; p++)
        if (prime[p])
            a.Add((long)p);
}
 
// Function to count integers upto k which are having
// perfect squares as factors. i is index of next
// prime number whose square needs to be checked.
// curr is current number whose square to be checked.
static long countSquares(long i, long cur,
                    long k, List<long> a)
{
    // variable to store square of prime
    long square = a[(int) i]*a[(int)(i)];
 
    long newCur = square * cur;
 
    // If value of greatest integer becomes zero
    if (newCur > k)
        return 0;
 
    // Applying inclusion-exclusion principle
 
    // Counting integers with squares as factor
    long cnt = k/(newCur);
 
    // Inclusion (Recur for next prime number)
    cnt += countSquares(i + 1, cur, k, a);
 
    // Exclusion (Recur for next prime number)
    cnt -= countSquares(i + 1, newCur, k, a);
 
    // Final count
    return cnt;
}
 
// Function to return nth square free number
static long squareFree(long n)
{
    // Computing primes and storing it in an array a[]
    List<long> a = new List<long>();
    SieveOfEratosthenes(a);
 
    // Applying binary search
    long low = 1;
    long high = MAX_RES;
 
    while (low < high)
    {
        long mid = low + (high - low)/2;
 
        // 'c' contains Number of square free numbers
        // less than or equal to 'mid'
        long c = mid - countSquares(0, 1, mid, a);
 
        // If c < n, then search right side of mid
        // else search left side of mid
        if (c < n)
            low = mid + 1;
        else
            high = mid;
    }
 
    // nth square free number
    return low;
}
 
// Driver code
public static void Main()
{
    int n = 10;
    Console.WriteLine(squareFree(n));
}
}
 
/* This code contributed by PrinciRaj1992 */

Javascript

<script>
 
// JavaScript Program to find the nth square free number
 
// Maximum prime number to be considered for square
// divisibility
let MAX_PRIME = 100000;
 
// Maximum value of result. We do
// binary search from 1 to MAX_RES
let MAX_RES = 2000000000;
 
function SieveOfEratosthenes(a)
{
    // Create a boolean array "prime[0..n]"
    // and initialize all entries it as
    // true. A value in prime[i] will
    // finally be false if i is Not
    // a prime, else true.
    let prime = new Array(MAX_PRIME + 1);
    for(let i=0;i<(MAX_PRIME + 1);i++)
    {
        prime[i]=true;
    }
  
    for (let p = 2; p * p <= MAX_PRIME; p++)
    {
        // If prime[p] is not changed,
        // then it is a prime
        if (prime[p] == true)
        {
            // Update all multiples of p
            for (let i = p * 2; i <= MAX_PRIME; i += p)
                prime[i] = false;
        }
    }
  
    // Store all prime numbers in a[]
    for (let p = 2; p <= MAX_PRIME; p++)
        if (prime[p])
            a.push(p);
}
 
// Function to count integers upto k which are having
// perfect squares as factors. i is index of next
// prime number whose square needs to be checked.
// curr is current number whose square to be checked.
function countSquares(i,cur,k,a)
{
    // variable to store square of prime
    let square = a[i]*a[i];
  
    let newCur = square*cur;
  
    // If value of greatest integer becomes zero
    if (newCur > k)
        return 0;
  
    // Applying inclusion-exclusion principle
  
    // Counting integers with squares as factor
    let cnt = Math.floor(k/(newCur));
  
    // Inclusion (Recur for next prime number)
    cnt += countSquares(i + 1, cur, k, a);
  
    // Exclusion (Recur for next prime number)
    cnt -= countSquares(i + 1, newCur, k, a);
  
    // Final count
    return cnt;
}
 
// Function to return nth square free number
function squareFree(n)
{
    // Computing primes and storing it in an array a[]
    let a = [];
    SieveOfEratosthenes(a);
  
    // Applying binary search
    let low = 1;
    let high = MAX_RES;
  
    while (low < high)
    {
        let mid = low + Math.floor((high - low)/2);
  
        // 'c' contains Number of square free numbers
        // less than or equal to 'mid'
        let c = mid - countSquares(0, 1, mid, a);
  
        // If c < n, then search right side of mid
        // else search left side of mid
        if (c < n)
            low = mid+1;
        else
            high = mid;
    }
  
    // nth square free number
    return low;
}
 
// Driver code
let n = 10;   
document.write(squareFree(n));
 
 
// This code is contributed by rag2127
 
</script>

Producción:  

14

Este artículo es una contribución de Rahul Agrawal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *