A Fortunate number is the smallest integer m > 1 such that, for a given positive integer n, pn + m is a prime number. Here pn is the product of the first n prime numbers, i.e prime factorials (or primorials) of order n.
For example :
p3 = 2 × 3 × 5 = 30 p4 = 2 × 3 × 5 × 7 = 210 p5 = 2 × 3 × 5 × 7 × 11 = 2310
Now, the smallest difference m between the prime factorial pn and the first prime number greater than pn for which (m > 1), is a prime number.
Examples :
Input : n = 3 Output : 7 Explanation : 7 must be added to the product of first n prime numbers to make the product prime. 2 x 3 x 5 = 30, need to add 7 to make it 37, which is a prime Input : n = 5 Output : 23
Approach : To find the nth Fortunate number, calculate the product of the first n prime numbers (primorial). Let this product be p. Then we find prime number greater than p and return the difference between the found prime number and p.
p4 + 13 = 223, where m = 13, a fortunate number p5 + 23 = 2333, where m = 23, a fortunate number p6 + 17 = 30047, where m = 17, a fortunate number
C++
// C++ program to find n-th Fortunate number#include <bits/stdc++.h>using namespace std;bool isPrime(int n){ // Corner cases if (n <= 1) return false; if (n <= 3) return true; // This is checked so that we can skip // middle five numbers in below loop if (n%2 == 0 || n%3 == 0) return false; for (int i=5; i*i<=n; i=i+6) if (n%i == 0 || n%(i+2) == 0) return false; return true;}// Function to Find primorial of order n // (product of first n prime numbers).long long int primorial(long long int n){ long long int p = 2; n--; for (int i = 3; n != 0; i++) { if (isPrime(i)) { p = p * i; n--; } i++; } return p;}// Function to find next prime number greater// than nlong long int findNextPrime(long long int n){ // Note that difference (or m) should be // greater than 1. long long int nextPrime = n + 2; // loop continuously until isPrime // returns true for a number above n while (true) { // Ignoring the prime number that // is 1 greater than n if (isPrime(nextPrime)) break; nextPrime++; } return nextPrime;}// Returns n-th Fortunate numberlong long int fortunateNumber(int n){ long long int p = primorial(n); return findNextPrime(p) - p;}// Driver functionint main(){ long long int n = 5; cout << fortunateNumber(n) << "\n"; return 0;} |
Java
// Java program to find n-th Fortunate numberimport java.lang.*;import java.util.*;class GFG{ public static boolean isPrime(int n) { // Corner cases if (n <= 1) return false; if (n <= 3) return true; // This is checked so that we can skip // middle five numbers in below loop if (n % 2 == 0 || n % 3 == 0) return false; for (int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false; return true; } // Function to Find primorial of order n // (product of first n prime numbers). public static int primorial(int n) { int p = 2; n--; for (int i = 3; n != 0; i++) { if (isPrime(i) == true) { p = p * i; n--; } i++; } return p; } // Function to find next prime number greater // than n public static int findNextPrime(int n) { // Note that difference (or m) should be // greater than 1. int nextPrime = n + 2; // loop continuously until isPrime // returns true for a number above n while (true) { // Ignoring the prime number that // is 1 greater than n if (isPrime(nextPrime) == true) break; nextPrime++; } return nextPrime; } // Returns n-th Fortunate number public static int fortunateNumber(int n) { int p = primorial(n); return findNextPrime(p)-p; } //Driver function public static void main (String[] args) { int n = 5; System.out.println(fortunateNumber(n)); }}/*This code is contributed by Akash Singh*/ |
Python3
# Python3 program to find# n-th Fortunate numberdef isPrime(n): # Corner cases if (n <= 1): return False if (n <= 3): return True # This is checked so that we can skip # middle five numbers in below loop if (n % 2 == 0 or n % 3 == 0): return False i = 5 while(i * i <= n): if (n % i == 0 or n % (i + 2) == 0): return False i += 6 return True# Function to Find primorial of order n # (product of first n prime numbers).def primorial(n): p = 2; n -= 1; i = 3 while(n != 0): if (isPrime(i)): p = p * i n -= 1 i += 1 return p# Function to find next prime # number greater than ndef findNextPrime(n): # Note that difference (or m) # should be greater than 1. nextPrime = n + 2 # loop continuously until isPrime # returns true for a number above n while (True): # Ignoring the prime number that # is 1 greater than n if (isPrime(nextPrime)): break nextPrime += 1 return nextPrime# Returns n-th Fortunate numberdef fortunateNumber(n): p = primorial(n) return findNextPrime(p) - p# Driver Coden = 5print(fortunateNumber(n))# This code is contributed by Anant Agarwal. |
C#
// C# program to find // n-th Fortunate numberusing System;class GFG{ public static bool isPrime(int n) { // Corner cases if (n <= 1) return false; if (n <= 3) return true; // This is checked so that // we can skip middle five // numbers in below loop if (n % 2 == 0 || n % 3 == 0) return false; for (int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false; return true; } // Function to Find primorial // of order n (product of first // n prime numbers). public static int primorial(int n) { int p = 2; n--; for (int i = 3; n != 0; i++) { if (isPrime(i) == true) { p = p * i; n--; } i++; } return p; } // Function to find next // prime number greater than n public static int findNextPrime(int n) { // Note that difference (or m) // should be greater than 1. int nextPrime = n + 2; // loop continuously until // isPrime returns true // for a number above n while (true) { // Ignoring the prime number // that is 1 greater than n if (isPrime(nextPrime) == true) break; nextPrime++; } return nextPrime; } // Returns n-th // Fortunate number public static int fortunateNumber(int n) { int p = primorial(n); return findNextPrime(p) - p; } // Driver Code public static void Main () { int n = 5; Console.WriteLine(fortunateNumber(n)); }}// This code is contributed// by anuj_67. |
PHP
<?php// PHP program to find n-th// Fortunate numberfunction isPrime($n){ // Corner cases if ($n <= 1) return false; if ($n <= 3) return true; // This is checked so that we can skip // middle five numbers in below loop if ($n % 2 == 0 || $n % 3 == 0) return false; for($i = 5; $i * $i <= $n; $i = $i + 6) if ($n % $i == 0 || $n % ($i + 2) == 0) return false; return true;}// Function to Find primorial of order n // (product of first n prime numbers).function primorial($n){ $p = 2; $n--; for ($i = 3; $n != 0; $i++) { if (isPrime($i)) { $p = $p * $i; $n--; } $i++; } return $p;}// Function to find next prime // number greater than nfunction findNextPrime($n){ // Note that difference (or m) // should be greater than 1. $nextPrime = $n + 2; // loop continuously until isPrime // returns true for a number above n while (true) { // Ignoring the prime number that // is 1 greater than n if (isPrime($nextPrime)) break; $nextPrime++; } return $nextPrime;}// Returns n-th Fortunate numberfunction fortunateNumber($n){ $p = primorial($n); return findNextPrime($p) - $p;} // Driver Code $n = 5; echo fortunateNumber($n) , "\n";// This code is contributed by ajit?> |
Javascript
<script>// JavaScript program to find n-th Fortunate number function isPrime(n) { // Corner cases if (n <= 1) return false; if (n <= 3) return true; // This is checked so that we can skip // middle five numbers in below loop if (n % 2 == 0 || n % 3 == 0) return false; for (let i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false; return true; } // Function to Find primorial of order n // (product of first n prime numbers). function primorial(n) { let p = 2; n--; for (let i = 3; n != 0; i++) { if (isPrime(i) == true) { p = p * i; n--; } i++; } return p; } // Function to find next prime number greater // than n function findNextPrime(n) { // Note that difference (or m) should be // greater than 1. let nextPrime = n + 2; // loop continuously until isPrime // returns true for a number above n while (true) { // Ignoring the prime number that // is 1 greater than n if (isPrime(nextPrime) == true) break; nextPrime++; } return nextPrime; } // Returns n-th Fortunate number function fortunateNumber(n) { let p = primorial(n); return findNextPrime(p)-p; }// Driver Code let n = 5; document.write(fortunateNumber(n));</script> |
Output:
23
Optimization : The above solution can be optimized using Sieve of Eratosthenes.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
