Given a number n, find the n-th square-free number. A number is square-free if it is not divisible by a perfect square other than 1.
Examples :
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.
Method 1 (Brute Force):
The idea is to iteratively check every number whether it is divisible by any perfect square number and increase the count whenever an square free number is encountered and returning the nth square free number.
Following is the implementation:
C++
// Program to find the nth square free number#include<bits/stdc++.h>using namespace std;// Function to find nth square free numberint 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 Programint main(){ int n = 10; cout << squareFree(n) << endl; return 0;} |
Java
// Java Program to find the nth square// free numberimport 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 numberusing 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 numberfunction 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> |
Output:
14
Time Complexity: O(n3/2)
Auxiliary Space: O(1)
Method 2 (Better approach):
Idea is to count square free numbers less than or equal to upper limit ‘k’ and then apply binary search to find n-th square free number. First, we calculate count of square numbers (numbers with squares as factors) upto ‘k’ and then subtracting that count from total numbers to get count of square free numbers upto ‘k’.
Explanation:
- If any integer has a perfect square as factor, then it is guaranteed that it has a square of prime as a factor too. So we need to count the integers less than or equal to ‘k’ which have square of primes as a factor.
For example, find number of integers who have either 4 or 9 as a factor upto ‘k’. It can done using Inclusion–exclusion principle. Using Inclusion–exclusion principle, total number of integers are [k/4] + [k/9] -[k/36] where [] is greatest integer function. - Recursively apply inclusion and exclusion till the value of greatest integer becomes zero. This step will return count of numbers with squares as factors.
- Apply binary search to find the nth square free number.
Following is the implementation of above algorithm:
C++
// Program to find the nth square free number#include<bits/stdc++.h>using namespace std;// Maximum prime number to be considered for square// divisibilityconst int MAX_PRIME = 100000;// Maximum value of result. We do binary search from 1// to MAX_RESconst 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 numberlong 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 Programint main(){ int n = 10; cout << squareFree(n) << endl; return 0;} |
Java
// Java Program to find the nth square free numberimport java.util.*;class GFG {// Maximum prime number to be considered for square// divisibilitystatic int MAX_PRIME = 100000;// Maximum value of result. We do // binary search from 1 to MAX_RESstatic 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 numberstatic 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 codepublic 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 numberimport syssys.setrecursionlimit(15000)# Maximum prime number to be considered for square# divisibilityMAX_PRIME = 100000;# Maximum value of result. We do binary search from 1# to MAX_RESMAX_RES = 2000000000def 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 numberdef 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 Programif __name__=='__main__': n = 10; print(squareFree(n)) # This code is contributed by rohitsingh07052. |
C#
// C# Program to find the nth square free numberusing System;using System.Collections.Generic;class GFG {// Maximum prime number to be considered // for square divisibilitystatic int MAX_PRIME = 100000;// Maximum value of result. We do // binary search from 1 to MAX_RESstatic 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 numberstatic 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 codepublic 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// divisibilitylet MAX_PRIME = 100000;// Maximum value of result. We do// binary search from 1 to MAX_RESlet 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 numberfunction 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 codelet n = 10; document.write(squareFree(n));// This code is contributed by rag2127</script> |
Output:
14
Time Complexity: O(MAX_PRIME * log(log(MAX_PRIME))) + O(sqrt(MAX_RES)) * log(MAX_RES))
Auxiliary Space: O(MAX_PRIME + sqrt(MAX_RES))
This article is contributed by Rahul Agrawal. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
