N번째 스마트번호
숫자 n이 주어지면 n번째 스마트 번호를 찾습니다(1 <=n <=1000). Smart number is a number which has at least three distinct prime factors. We are given an upper limit on value of result as MAX For example 30 is 1st smart number because it has 2 3 5 as it's distinct prime factors. 42 is 2nd smart number because it has 2 3 7 as it's distinct prime factors. 예:
Input : n = 1 Output: 30 // three distinct prime factors 2 3 5 Input : n = 50 Output: 273 // three distinct prime factors 3 7 13 Input : n = 1000 Output: 2664 // three distinct prime factors 2 3 37권장 사항: 해결해 보세요. 관행 먼저 솔루션으로 넘어가기 전에
아이디어는 다음을 기반으로합니다. 에라토스테네스의 체 . 소수를 추적하기 위해 배열을 사용하여 배열 prime[]을 사용합니다. 또한 지금까지 본 소인수 개수를 추적하기 위해 동일한 배열을 사용합니다. 개수가 3에 도달할 때마다 결과에 숫자를 추가합니다.
- primes[] 배열을 가져와 0으로 초기화합니다.
- 이제 우리는 첫 번째 소수가 i = 2라는 것을 알았습니다. 따라서 primes[2] = 1로 표시하십시오. primes[i] = 1은 'i'가 소수임을 나타냅니다.
- 이제 primes[] 배열을 순회하고 조건 primes[j] -= 1로 'i'의 모든 배수를 표시하고 'j'가 'i'의 배수인 경우 조건 primes[j]+3 = 0을 확인합니다. 왜냐하면 primes[j]가 -3이 될 때마다 이전에는 세 개의 개별 소인수 배수였음을 나타내기 때문입니다. 조건이 있는 경우 소수[j]+3=0 true가 되면 'j'가 스마트 번호임을 의미하므로 이를 result[] 배열에 저장합니다.
- 이제 배열 결과[]를 정렬하고 결과[n-1]을 반환합니다.
아래는 위의 아이디어를 구현한 것입니다.
C++ // C++ implementation to find n'th smart number #include using namespace std ; // Limit on result const int MAX = 3000 ; // Function to calculate n'th smart number int smartNumber ( int n ) { // Initialize all numbers as not prime int primes [ MAX ] = { 0 }; // iterate to mark all primes and smart number vector < int > result ; // Traverse all numbers till maximum limit for ( int i = 2 ; i < MAX ; i ++ ) { // 'i' is maked as prime number because // it is not multiple of any other prime if ( primes [ i ] == 0 ) { primes [ i ] = 1 ; // mark all multiples of 'i' as non prime for ( int j = i * 2 ; j < MAX ; j = j + i ) { primes [ j ] -= 1 ; // If i is the third prime factor of j // then add it to result as it has at // least three prime factors. if ( ( primes [ j ] + 3 ) == 0 ) result . push_back ( j ); } } } // Sort all smart numbers sort ( result . begin () result . end ()); // return n'th smart number return result [ n -1 ]; } // Driver program to run the case int main () { int n = 50 ; cout < < smartNumber ( n ); return 0 ; }
Java // Java implementation to find n'th smart number import java.util.* ; import java.lang.* ; class GFG { // Limit on result static int MAX = 3000 ; // Function to calculate n'th smart number public static int smartNumber ( int n ) { // Initialize all numbers as not prime Integer [] primes = new Integer [ MAX ] ; Arrays . fill ( primes new Integer ( 0 )); // iterate to mark all primes and smart // number Vector < Integer > result = new Vector <> (); // Traverse all numbers till maximum // limit for ( int i = 2 ; i < MAX ; i ++ ) { // 'i' is maked as prime number // because it is not multiple of // any other prime if ( primes [ i ] == 0 ) { primes [ i ] = 1 ; // mark all multiples of 'i' // as non prime for ( int j = i * 2 ; j < MAX ; j = j + i ) { primes [ j ] -= 1 ; // If i is the third prime // factor of j then add it // to result as it has at // least three prime factors. if ( ( primes [ j ] + 3 ) == 0 ) result . add ( j ); } } } // Sort all smart numbers Collections . sort ( result ); // return n'th smart number return result . get ( n - 1 ); } // Driver program to run the case public static void main ( String [] args ) { int n = 50 ; System . out . println ( smartNumber ( n )); } } // This code is contributed by Prasad Kshirsagar
Python3 # Python3 implementation to find # n'th smart number # Limit on result MAX = 3000 ; # Function to calculate n'th # smart number def smartNumber ( n ): # Initialize all numbers as not prime primes = [ 0 ] * MAX ; # iterate to mark all primes # and smart number result = []; # Traverse all numbers till maximum limit for i in range ( 2 MAX ): # 'i' is maked as prime number because # it is not multiple of any other prime if ( primes [ i ] == 0 ): primes [ i ] = 1 ; # mark all multiples of 'i' as non prime j = i * 2 ; while ( j < MAX ): primes [ j ] -= 1 ; # If i is the third prime factor of j # then add it to result as it has at # least three prime factors. if ( ( primes [ j ] + 3 ) == 0 ): result . append ( j ); j = j + i ; # Sort all smart numbers result . sort (); # return n'th smart number return result [ n - 1 ]; # Driver Code n = 50 ; print ( smartNumber ( n )); # This code is contributed by mits
C# // C# implementation to find n'th smart number using System.Collections.Generic ; class GFG { // Limit on result static int MAX = 3000 ; // Function to calculate n'th smart number public static int smartNumber ( int n ) { // Initialize all numbers as not prime int [] primes = new int [ MAX ]; // iterate to mark all primes and smart // number List < int > result = new List < int > (); // Traverse all numbers till maximum // limit for ( int i = 2 ; i < MAX ; i ++ ) { // 'i' is maked as prime number // because it is not multiple of // any other prime if ( primes [ i ] == 0 ) { primes [ i ] = 1 ; // mark all multiples of 'i' // as non prime for ( int j = i * 2 ; j < MAX ; j = j + i ) { primes [ j ] -= 1 ; // If i is the third prime // factor of j then add it // to result as it has at // least three prime factors. if ( ( primes [ j ] + 3 ) == 0 ) result . Add ( j ); } } } // Sort all smart numbers result . Sort (); // return n'th smart number return result [ n - 1 ]; } // Driver program to run the case public static void Main () { int n = 50 ; System . Console . WriteLine ( smartNumber ( n )); } } // This code is contributed by mits
PHP // PHP implementation to find n'th smart number // Limit on result $MAX = 3000 ; // Function to calculate n'th smart number function smartNumber ( $n ) { global $MAX ; // Initialize all numbers as not prime $primes = array_fill ( 0 $MAX 0 ); // iterate to mark all primes and smart number $result = array (); // Traverse all numbers till maximum limit for ( $i = 2 ; $i < $MAX ; $i ++ ) { // 'i' is maked as prime number because // it is not multiple of any other prime if ( $primes [ $i ] == 0 ) { $primes [ $i ] = 1 ; // mark all multiples of 'i' as non prime for ( $j = $i * 2 ; $j < $MAX ; $j = $j + $i ) { $primes [ $j ] -= 1 ; // If i is the third prime factor of j // then add it to result as it has at // least three prime factors. if ( ( $primes [ $j ] + 3 ) == 0 ) array_push ( $result $j ); } } } // Sort all smart numbers sort ( $result ); // return n'th smart number return $result [ $n - 1 ]; } // Driver program to run the case $n = 50 ; echo smartNumber ( $n ); // This code is contributed by mits ?>
JavaScript < script > // JavaScript implementation to find n'th smart number // Limit on result const MAX = 3000 ; // Function to calculate n'th smart number function smartNumber ( n ) { // Initialize all numbers as not prime let primes = new Array ( MAX ). fill ( 0 ); // iterate to mark all primes and smart number let result = []; // Traverse all numbers till maximum limit for ( let i = 2 ; i < MAX ; i ++ ) { // 'i' is maked as prime number because // it is not multiple of any other prime if ( primes [ i ] == 0 ) { primes [ i ] = 1 ; // mark all multiples of 'i' as non prime for ( let j = i * 2 ; j < MAX ; j = j + i ) { primes [ j ] -= 1 ; // If i is the third prime factor of j // then add it to result as it has at // least three prime factors. if ( ( primes [ j ] + 3 ) == 0 ) result . push ( j ); } } } // Sort all smart numbers result . sort (( a b )=> a - b ); // return n'th smart number return result [ n - 1 ]; } // Driver program to run the case let n = 50 ; document . write ( smartNumber ( n )); // This code is contributed by shinjanpatra < /script>
산출:
273
시간 복잡도: O(MAX)
보조공간 : O(MAX)
퀴즈 만들기
