Cari nombor bertuah ke-

.

Sebagai contoh, untuk mengira nombor bertuah ketiga, mula-mula hitung hasil darab 3 nombor perdana pertama (2, 3, 5), iaitu 30. Menambah 2 memberi kita 32, iaitu nombor genap, dan menambah 3 memberi kita 33, iaitu gandaan 3. Integer hingga 6 juga boleh dikecualikan. Menambah 7 memberi kita 37, yang merupakan nombor perdana. Oleh itu, 7 adalah nombor bertuah ketiga.

Nombor bertuah untuk nombor primitif pertama ialah - 3, 5, 7, 13, 23, 17, 19, 23, 37, 61, 67, 61, 71, 47, 107, 59, 61, 109….

Pernyataan Masalah

Diberi nombor n. Cari nombor bertuah ke-.

Contoh 1

Input: n = 3

Output: 7

Penjelasan

- Produk 3 angka harga pertama -

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

Contoh 2

Input: n = 7

Output: 19

Penjelasan - Produk daripada 7 nombor perdana pertama -

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

Kaedah 1: Kaedah asal

Cara mudah untuk menyelesaikan masalah ini adalah dengan mengira pn#, hasil darab n nombor perdana pertama, dan kemudian cari perbezaan antara pn# dan nombor perdana seterusnya. Perbezaan yang diperolehi akan menjadi nombor bertuah. pseudokod

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

Contoh: Pelaksanaan C++

Dalam program di bawah, nombor bertuah dikira dengan mengira primitif bagi n nombor perdana pertama dan mencari nombor perdana seterusnya selepas primitif. Nombor bertuah ialah perbezaan antara nombor perdana seterusnya dan nombor 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;
}

Output

15th Fortunate number : 107

Kerumitan masa - O(nsqrt(n)), dengan kerumitan fungsi prime() ialah O(sqrt(n)) dan kerumitan gelung for dalam nthFortunate() ialah O(nsqrt(n)).

Kerumitan ruang - O(1)

Kaedah 2: Ayak Eratosthenes

Ayak Eratosthenes digunakan untuk membawa semua nombor perdana sehingga had, yang memberikan kita nilai MAX. Dalam kaedah ini, kami mencipta tatasusunan boolean yang mengandungi semua entri benar dan menandakan semua indeks bukan perdana sebagai palsu. Kemudian darab n nombor perdana pertama dalam tatasusunan untuk mendapatkan hasil darab n nombor perdana pertama. Kemudian sama dengan kaedah sebelumnya, mulakan pada 2 dan tambah 1 pada produk untuk mendapatkan nombor perdana seterusnya. Perbezaan antara nombor perdana seterusnya dan produk adalah nombor bertuah yang diperlukan.

pseudokod

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

Contoh: Pelaksanaan C++

Dalam program berikut, tatasusunan perdana Boolean bersaiz MAX merekodkan semua nombor perdana sebelum MAX. Yang asal kemudiannya ditemui dengan mendarab n nombor perdana pertama. Kemudian sama dengan kaedah sebelumnya, cari nextPrime. Perbezaan antara nextPrime dan Product ialah nombor bertuah.

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

Output

15th Fortunate number : 107

Kerumitan masa - O(n log(log(n)))

Kerumitan ruang - O(MAX)

Kesimpulan

Ringkasnya, nombor bertuah ke-1 boleh didapati dalam dua cara berikut.

Kaedah asas: Cari hasil darab n nombor perdana pertama, dan kira nombor perdana seterusnya berdasarkan hasil darab. Perbezaan antara nombor perdana dan produk ialah nombor bertuah ke-n.

Ayak Eratosthenes: Cari semua nombor perdana yang mencapai had tertentu, dan kemudian kira produk dengan nombor perdana seterusnya untuk mencari nombor bertuah.

Kedua-dua kaedah adalah cekap untuk nilai n yang lebih kecil hanya disebabkan oleh kekangan saiz yang berubah-ubah. Untuk nilai yang lebih besar, penyelesaian yang lebih cekap dan dioptimumkan diperlukan.

Atas ialah kandungan terperinci Cari nombor bertuah ke-. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!