Finden Sie die n-te Glückszahl

Glückszahl – Es ist die kleinste ganze Zahl, sodass m > 1 ist. Für eine gegebene positive ganze Zahl n ist pn# + m eine Primzahl, wobei pn# die Produktprimzahl des ersten n ist.

Um beispielsweise die dritte Glückszahl zu berechnen, berechnen Sie zunächst das Produkt der ersten drei Primzahlen (2, 3, 5), also 30. Die Addition von 2 ergibt 32, was eine gerade Zahl ist, und die Addition von 3 ergibt 33, was ein Vielfaches von 3 ist. Auch ganze Zahlen bis 6 können ausgeschlossen werden. Die Addition von 7 ergibt 37, was eine Primzahl ist. Daher ist 7 die dritte Glückszahl.

Die Glückszahl für die erste Grundzahl ist -

3, 5, 7, 13, 23, 17, 19, 23, 37, 61, 67, 61, 71, 47, 107, 59, 61, 109….

Problemstellung

Gegeben eine Zahl n. Finden Sie die n-te Glückszahl.

Beispiel 1

Input: n = 3

Output: 7

Erklärung - Produkt der ersten 3 Preisangaben -

2  3  5 = 30
30 + 7 = 37, a prime number.

Beispiel 2

Input: n = 7

Output: 19

Erklärung – Produkt der ersten 7 Primzahlen –

2  3  5  7  11  13  17 = 510510
510510 + 19 = 510529, a prime number.

Methode 1: Originalmethode

Eine einfache Möglichkeit, dieses Problem zu lösen, besteht darin, zunächst pn#, das Produkt der ersten n Primzahlen, zu berechnen und dann die Differenz zwischen pn# und der nächsten Primzahl zu ermitteln. Die erhaltene Differenz ist eine Glückszahl.

Pseudocode

procedure prime (num)
   if num <= 1
      ans = TRUE
   end if
   for i = 2 to sqrt(num)
      if i is a factor of num
         ans = false
      end if
   ans = true
end procedure
procedure nthFortunate (n)
   prod = 1
   count = 0
   for i = 2 to count < n
      if i is prime
         prod = prod * i
         count = count + 1
      end if
   nextPrime = prod + 2
   while nextPrime is not prime
      nextPrime = next Prime + 1
   ans = nextPrime - prod
end procedure

Beispiel: C++-Implementierung

Im folgenden Programm wird die Glückszahl berechnet, indem die Grundzahlen der ersten n Primzahlen berechnet und die nächste Primzahl nach der Grundzahl ermittelt wird. Die Glückszahl ist die Differenz zwischen der nächsten Primzahl und der Grundzahl.

#include <bits/stdc++.h>
using namespace std;

// Function to find if a number is prime or not
bool prime(unsigned long long int num){
   if (num <= 1)
      return true;
   for (int i = 2; i <= sqrt(num); i++){
      if (num % i == 0)
         return false;
   }
   return true;
}

// Function to find the nth Fortunate number
unsigned long long int nthFortunate(int n){
   long long int prod = 1, count = 0;
   
   // Calculating product/primorial of first n prime numbers
   for (int i = 2; count < n; i++){
      if (prime(i)){
         prod *= i;
         count++;
      }
   }
   
   // Find the next prime greater than the product of n prime numbers
   unsigned long long int nextPrime = prod + 2;
   while (!prime(nextPrime)){
      nextPrime++;
   }
   
   // Fortunate number is the difference between prime and primorial
   unsigned long long int ans = nextPrime - prod;
   return ans;
}
int main(){
   int n = 15;
   cout << n << "th Fortunate number : " << nthFortunate(n);
   return 0;
}

Ausgabe

15th Fortunate number : 107

Zeitkomplexität – O(nsqrt(n)), wobei die Komplexität der Funktion prime() O(sqrt(n)) und die Komplexität der for-Schleife in nthFortunate() O(nsqrt(n)) beträgt.

Raumkomplexität – O(1)

Methode 2: Sieb von Eratosthenes

Das Sieb des Eratosthenes wird verwendet, um alle Primzahlen auf einen Grenzwert zu bringen, der uns einen Wert von MAX gibt. Bei dieser Methode erstellen wir ein boolesches Array, das alle wahren Einträge enthält, und markieren alle Nicht-Primzahl-Indizes als falsch. Dann multiplizieren Sie die ersten n Primzahlen im Array, um das Produkt der ersten n Primzahlen zu erhalten. Beginnen Sie dann ähnlich wie bei der vorherigen Methode bei 2 und addieren Sie 1 zum Produkt, um die nächste Primzahl zu erhalten. Die Differenz zwischen der nächsten Primzahl und dem Produkt ist die benötigte Glückszahl.

Pseudocode

procedure nthFortunate (n)
   MAX is set
   prime[MAX] = {true}
   prime[0] = false
   prime[1] = false
   for i = 1 to i*i <= MAX
      if prime[i]
         for j = i*i to MAX with j = j + i in each iteration
            prime [j] = false
      end if
   prod = 1
   count = 0
   for i = 2 to count < n
      if prime[i]
         prod = prod * i
         count = count + 1
      end if
   nextPrime = prod + 2
   while nextPrime is not prime
      nextPrime = nextPrime + 1
   ans = nextPrime - prod
end procedure

Beispiel: C++-Implementierung

Im folgenden Programm zeichnet ein boolesches Primzahlarray der Größe MAX alle Primzahlen vor MAX auf. Das Original wird dann durch Multiplikation der ersten n Primzahlen ermittelt. Suchen Sie dann ähnlich wie bei der vorherigen Methode nextPrime. Der Unterschied zwischen nextPrime und Product ist die Glückszahl.

#include <bits/stdc++.h>
using namespace std;

// Function to find the nth Fortunate number
unsigned long long int nthFortunate(int n){

   // Setting upper limit for Sieve of Eratosthenes
   const unsigned long long int MAX = 1000000000;
   vector<bool> prime(MAX, true);
   prime[0] = prime[1] = false;
   
   // Sieve of Eratosthenes to find all primes up to MAX
   for (unsigned long long int i = 2; i * i <= MAX; i++){
      if (prime[i]){
      
         // Setting all the multiples of i to false
         for (int j = i * i; j <= MAX; j += i){
            prime[j] = false;
         }
      }
   }
   
   // Find the first n primes and calculate their product
   unsigned long long int prod = 1, count = 0;
   for (unsigned long long int i = 2; count < n; i++){
      if (prime[i]){
         prod *= i;
         count++;
      }
   }
   
   // Find next prime greater than product
   unsigned long long int nextPrime = prod + 2;
   while (!prime[nextPrime])
      nextPrime++;
      
   // Fortunate number is difference between prime and product
   return nextPrime - prod;
}
int main(){
   int n = 25;
   cout << n << "th Fortunate number : " << nthFortunate(n);
   return 0;
}

Ausgabe

15th Fortunate number : 107

Zeitkomplexität – O(n log(log(n)))

Raumkomplexität – O(MAX)

Fazit

Zusammenfassend lässt sich sagen, dass die n-te Glückszahl auf die folgenden zwei Arten gefunden werden kann.

Elementarmethode: Finden Sie das Produkt der ersten n Primzahlen und berechnen Sie die nächste Primzahl basierend auf dem Produkt. Die Differenz zwischen der Primzahl und dem Produkt ist die n-te Glückszahl.

Sieb des Eratosthenes: Finden Sie alle Primzahlen, die eine bestimmte Grenze erreichen, und berechnen Sie dann das Produkt mit der nächsten Primzahl, um die Glückszahl zu finden.

Beide Methoden sind für kleinere Werte von n einfach aufgrund der Größenbeschränkungen der Variablen effizient. Für größere Werte sind effizientere und optimierte Lösungen erforderlich.

Das obige ist der detaillierte Inhalt vonFinden Sie die n-te Glückszahl. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!