Encuentra el n-ésimo número de la suerte

Un número afortunado es el entero más pequeño m > 1 tal que, para un entero positivo dado n, p n + m es un número primo. Aquí p n es el producto de los n primeros números primos, es decir, factores primos (o primoriales ) de orden n.
Por ejemplo : 
 

p3 = 2 × 3 × 5 = 30
p4 = 2 × 3 × 5 × 7 = 210
p5 = 2 × 3 × 5 × 7 × 11 = 2310

Ahora bien, la menor diferencia m entre el factorial primo p n y el primer número primo mayor que p n para el cual (m > 1), es un número primo.
Ejemplos: 
 

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

Planteamiento : Para encontrar el enésimo número de la Fortuna, calcule el producto de los primeros n números primos (primoriales). Que este producto sea p. Luego encontramos un número primo mayor que p y devolvemos la diferencia entre el número primo encontrado y 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 n
long 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 number
long long int fortunateNumber(int n)
{
   long long int p = primorial(n);
   return findNextPrime(p) - p;
}
 
// Driver function
int main()
{
    long long int n = 5;
    cout << fortunateNumber(n) << "\n";
    return 0;
}

Java

// Java program to find n-th Fortunate number
import 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 number
 
def 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 n
def 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 number
def fortunateNumber(n):
    p = primorial(n)
    return findNextPrime(p) - p
 
# Driver Code
n = 5
print(fortunateNumber(n))
 
# This code is contributed by Anant Agarwal.

C#

// C# program to find
// n-th Fortunate number
using 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 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($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 n
function 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 number
function 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>
Producción: 

23

 

Optimización : La solución anterior se puede optimizar utilizando Tamiz de Eratóstenes
 

Publicación traducida automáticamente

Artículo escrito por SaagnikAdhikary y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *