Trouvez le nième numéro porte-bonheur

Lucky Number - C'est le plus petit entier tel que m > 1, pour un entier positif donné n, pn# + m est un nombre premier, où pn# est le produit premier du premier n.

Par exemple, pour calculer le troisième nombre porte-bonheur, calculez d'abord le produit des 3 premiers nombres premiers (2, 3, 5), qui est 30. Ajouter 2 nous donne 32, qui est un nombre pair, et ajouter 3 nous donne 33, qui est un multiple de 3. Les entiers jusqu'à 6 peuvent également être exclus. Ajouter 7 nous donne 37, qui est un nombre premier. Le 7 est donc le troisième chiffre porte-bonheur.

Le chiffre porte-bonheur du premier chiffre primitif est -

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

Énoncé du problème

Étant donné un numéro n. Trouvez le nième numéro porte-bonheur.

Exemple 1

Input: n = 3

Output: 7

Explication - Produit des 3 premiers chiffres de prix -

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

Exemple 2

Input: n = 7

Output: 19

Explication - Produit des 7 premiers nombres premiers -

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

Méthode 1 : Méthode originale

Un moyen simple de résoudre ce problème consiste d'abord à calculer pn#, le produit des n premiers nombres premiers, puis à trouver la différence entre pn# et le nombre premier suivant. La différence obtenue sera un chiffre porte-bonheur.

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

Exemple : implémentation C++

Dans le programme ci-dessous, le nombre porte-bonheur est calculé en calculant les primitives des n premiers nombres premiers et en trouvant le nombre premier suivant après la primitive. Le nombre porte-bonheur est la différence entre le nombre premier suivant et le nombre primitif.

#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;
}

Sortie

15th Fortunate number : 107

Complexité temporelle - O(nsqrt(n)), où la complexité de la fonction prime() est O(sqrt(n)) et la complexité de la boucle for dans nthFortunate() est O(nsqrt(n)).

Complexité spatiale - O(1)

Méthode 2 : Tamis d'Ératosthène

Le Tamis d'Ératosthène est utilisé pour amener tous les nombres premiers jusqu'à une limite, où l'on nous donnera une valeur de MAX. Dans cette méthode, nous créons un tableau booléen contenant toutes les entrées vraies et marquons tous les index non premiers comme faux. Multipliez ensuite les n premiers nombres premiers du tableau pour obtenir le produit des n premiers nombres premiers. Ensuite, comme pour la méthode précédente, commencez par 2 et ajoutez 1 au produit pour obtenir le nombre premier suivant. La différence entre le nombre premier suivant et le produit est le nombre porte-bonheur requis.

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

Exemple : implémentation C++

Dans le programme suivant, un tableau premier booléen de taille MAX enregistre tous les nombres premiers avant MAX. L'original est ensuite trouvé en multipliant les n premiers nombres premiers. Ensuite, comme pour la méthode précédente, recherchez nextPrime. La différence entre nextPrime et Product est le numéro porte-bonheur.

#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;
}

Sortie

15th Fortunate number : 107

Complexité temporelle - O(n log(log(n)))

Complexité spatiale - O(MAX)

Conclusion

En résumé, le nième numéro porte-bonheur peut être trouvé des deux manières suivantes.

Méthode élémentaire : trouvez le produit des n premiers nombres premiers et calculez le nombre premier suivant en fonction du produit. La différence entre le nombre premier et le produit est le nième nombre porte-bonheur.

Tamis d'Eratosthène : trouvez tous les nombres premiers qui atteignent une certaine limite, puis calculez le produit avec le nombre premier suivant pour trouver le nombre porte-bonheur.

Les deux méthodes sont efficaces pour les valeurs plus petites de n simplement en raison de limitations de taille variable. Pour des valeurs plus élevées, des solutions plus efficaces et optimisées sont nécessaires.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!