N 'th Smart Number | C ++ implementation to find n 'th smart number ; Limit on result ; Function to calculate n 'th smart number ; Initialize all numbers as not prime ; iterate to mark all primes and smart number ; Traverse all numbers till maximum limit ; ' i ' is maked as prime number because it is not multiple of any other prime ; mark all multiples of ' i ' as non prime ; If i is the third prime factor of j then add it to result as it has at least three prime factors . ; Sort all smart numbers ; return n 'th smart number ; Driver program to run the case
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int MAX = 3000 ; int smartNumber ( int n ) { int primes [ MAX ] = { 0 } ; vector < int > result ; for ( int i = 2 ; i < MAX ; i ++ ) { if ( primes [ i ] == 0 ) { primes [ i ] = 1 ; for ( int j = i * 2 ; j < MAX ; j = j + i ) { primes [ j ] -= 1 ; if ( ( primes [ j ] + 3 ) == 0 ) result . push_back ( j ) ; } } } sort ( result . begin ( ) , result . end ( ) ) ; return result [ n - 1 ] ; } int main ( ) { int n = 50 ; cout << smartNumber ( n ) ; return 0 ; }