Biorąc pod uwagę liczbę n, znajdź n-tą liczbę inteligentną (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. Przykłady:
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 37Zalecane: Proszę o rozwiązanie PRAKTYKA najpierw, zanim przejdziesz do rozwiązania.
Pomysł opiera się na Sito Eratostenesa . Używamy tablicy, aby używać tablicy prime[] do śledzenia liczb pierwszych. Używamy również tej samej tablicy do śledzenia liczby czynników pierwszych zaobserwowanych do tej pory. Kiedy liczba osiągnie 3, dodajemy liczbę do wyniku.
Java do string
- Weź tablicę primes[] i zainicjuj ją wartością 0.
- Teraz wiemy, że pierwszą liczbą pierwszą jest i = 2, więc zaznacz liczby pierwsze[2] = 1 tj.; liczby pierwsze[i] = 1 oznacza, że „i” jest liczbą pierwszą.
- Teraz przejdź przez tablicę liczb pierwszych[] i zaznacz wszystkie wielokrotności „i” według liczb pierwszych warunku[j] -= 1, gdzie „j” jest wielokrotnością „i” i sprawdź liczby pierwsze warunków[j]+3 = 0, ponieważ ilekroć liczby pierwsze[j] mają wartość -3, oznacza to, że poprzednio była to wielokrotność trzech różnych czynników pierwszych. Jeśli warunek liczby pierwsze[j]+3=0 staje się prawdą, co oznacza, że „j” jest liczbą inteligentną, więc zapisz ją w tablicy wynik[].
- Teraz posortuj wynik tablicy [] i zwróć wynik [n-1].
Poniżej realizacja powyższego pomysłu.
C++// C++ implementation to find n'th smart number #include
// 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 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# 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 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$MAX0); // 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 ?> <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((ab)=>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>
Wyjście:
ups
273
Złożoność czasowa: O(MAX)
Przestrzeń pomocnicza: O(MAX)