N'T SLIMME NUMMER

Gegeven een getal n, vind het n-de slimme getal (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. Voorbeelden:

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

Aanbevolen: los het op OEFENING eerst voordat u verdergaat met de oplossing.

Het idee is gebaseerd op Zeef van Eratosthenes . We gebruiken een array om een array prime[] te gebruiken om priemgetallen bij te houden. We gebruiken dezelfde array ook om het aantal priemfactoren bij te houden dat we tot nu toe hebben gezien. Wanneer de telling 3 bereikt, voegen we het getal toe aan het resultaat.

Neem een array primes[] en initialiseer deze met 0.
Nu weten we dat het eerste priemgetal i = 2 is, dus markeer priemgetallen[2] = 1, d.w.z.; priemgetallen[i] = 1 geeft aan dat 'i' een priemgetal is.
Doorloop nu de reeks priemgetallen[] en markeer alle veelvouden van 'i' met de voorwaarde priemgetallen[j] -= 1 waarbij 'j' een veelvoud is van 'i' en controleer de voorwaarde priemgetallen[j]+3 = 0, want telkens wanneer priemgetallen[j] -3 worden, geeft dit aan dat het voorheen een veelvoud van drie verschillende priemfactoren was. Indien voorwaarde priemgetallen[j]+3=0 wordt waar, wat betekent dat 'j' een slim getal is, dus sla het op in een arrayresultaat[].
Sorteer nu arrayresultaat[] en retourneer resultaat[n-1].

Hieronder ziet u de implementatie van bovenstaand idee.

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# 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$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  ?>

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((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>

Uitgang:

Tijdcomplexiteit: O(MAX)
Hulpruimte: O (MAX)

TechCodeview