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