Finding the n-th Fortune Number in C++
In this article, we will discuss how to find the n-th Fortune Number in C++. Before going to its implementation, we will learn about the Fortunate Number in C++.
What are the Fortunate Numbers?
A Fortunate number (m) is the smallest integer greater than 1 that, when added to the product of the first n prime numbers (pn), results in a prime number. In other words: pn + m is prime, where pn = (2 * 3 * ... * nth prime).
Applications and Use Cases
While Fortunate numbers aren't as widely used in cryptography or other practical applications as some other number sequences, they can be of interest for:
- Number Theory Research: Contributing to the study of prime numbers and their distribution.
- Recreational Mathematics: Providing an intriguing number sequence for exploration.
- Algorithmic Challenges: Practicing techniques for prime number generation and primality testing.
Example:
Here's a C++ function to find the n-th Fortunate Number, combining clarity, efficiency, and error handling:
#include#include using namespace std; // Efficient primality test using trial division (up to the square root) bool isPrime(int n) { if (n <= 1) { return false; // 1 or less are not prime } if (n <= 3) { return true; // 2 and 3 are prime } if (n % 2 == 0 || n % 3 == 0) { return false; // Divisible by 2 or 3 } for (int i = 5; i * i <= n; i += 6) { if (n % i == 0 || n % (i + 2) == 0) { return false; // Divisible by a number in the sequence 5, 7, 11, 13, ... } } return true; } // Function to find the n-th Fortunate Number int nthFortunateNumber(int n) { if (n <= 0) { throw invalid_argument("n must be a positive integer."); } vector primes; // Store the first n prime numbers // Generate the first n prime numbers efficiently using the Sieve of Eratosthenes int num = 2; while (primes.size() < n) { if (isPrime(num)) { primes.push_back(num); } num++; } // Calculate the product of the first n prime numbers (primorial) long long primorial = 1; for (int prime : primes) { primorial *= prime; // Check for overflow to prevent incorrect calculations if (primorial < 0) { throw runtime_error("Overflow occurred during primorial calculation."); } } // Find the next prime number greater than the primorial int candidate = primorial + 1; while (!isPrime(candidate)) { candidate++; } return candidate - primorial; // Return the difference, which is the n-th Fortunate Number } int main() { int n; cout << "Enter the value of n (positive integer): "; cin >> n; try { int fortunateNumber = nthFortunateNumber(n); cout << "The " << n << "-th Fortunate Number is: " << fortunateNumber << endl; } catch (const invalid_argument& e) { cerr << "Error: " << e.what() << endl; return 1; } catch (const runtime_error& e) { cerr << "Error: " << e.what() << endl; return 1; } return 0; }
Output:
← Prev Next →