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:
- 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. - 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.
- 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