Comprobar si N es primo fuerte

Posted on by Rudeus Greyrat

Dado un entero positivo N , la tarea es comprobar si N es un número primo fuerte o no. 
En teoría de números, un primo fuerte es un número primo que es mayor que la media aritmética de los números primos más cercanos, es decir, los números primos siguientes y anteriores. 
Los primeros números primos fuertes son 11, 17, 29, 37, 41, 59, 67, 71, … 
Un primo fuerte P n se puede representar como- 
 

Strong prime

donde n es su índice en el conjunto ordenado de números primos.

Ejemplos: 

Entrada: N = 11 
Salida: Sí 
11 es el quinto número primo, la media aritmética del cuarto y sexto número primo, es decir, 7 y 13 es 10. 
11 es mayor que 10, por lo que 11 es un número primo fuerte. 

Entrada: N = 13 
Salida: No 
13 es el sexto número primo, la media aritmética del quinto (11) y el séptimo (17) es (11 + 17) / 2 = 14. 
13 es más pequeño que 14, por lo que 13 no es un número primo fuerte . 
 

Acercarse: 

  • Si N no es un número primo o es el primer número primo, es decir , 2 , imprima No.
  • De lo contrario, busque los primos más cercanos a N (uno a la izquierda y otro a la derecha) y almacene su media aritmética en mean . 
    • Si N > significa , imprima Sí .
    • De lo contrario , imprima No.

A continuación se muestra la implementación del enfoque anterior: 

C++

// C++ program to check if given number is strong prime
#include <bits/stdc++.h>
using namespace std;
 
// Utility function to check
// if a number is prime or not
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 that returns true if n is a strong prime
static bool isStrongPrime(int n)
{
    // If n is not a prime number or
    // n is the first prime then return false
    if (!isPrime(n) || n == 2)
        return false;
 
    // Initialize previous_prime to n - 1
    // and next_prime to n + 1
    int previous_prime = n - 1;
    int next_prime = n + 1;
 
    // Find next prime number
    while (!isPrime(next_prime))
        next_prime++;
 
    // Find previous prime number
    while (!isPrime(previous_prime))
        previous_prime--;
 
    // Arithmetic mean
    int mean = (previous_prime + next_prime) / 2;
 
    // If n is a strong prime
    if (n > mean)
        return true;
    else
        return false;
}
 
// Driver code
int main()
{
 
    int n = 11;
 
    if (isStrongPrime(n))
        cout << "Yes";
    else
        cout << "No";
 
    return 0;
}

Java

// Java program to check if given number is strong prime
class GFG {
 
    // Utility function to check
    // if a number is prime or not
    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 that returns true if n is a strong prime
    static boolean isStrongPrime(int n)
    {
        // If n is not a prime number or
        // n is the first prime then return false
        if (!isPrime(n) || n == 2)
            return false;
 
        // Initialize previous_prime to n - 1
        // and next_prime to n + 1
        int previous_prime = n - 1;
        int next_prime = n + 1;
 
        // Find next prime number
        while (!isPrime(next_prime))
            next_prime++;
 
        // Find previous prime number
        while (!isPrime(previous_prime))
            previous_prime--;
 
        // Arithmetic mean
        int mean = (previous_prime + next_prime) / 2;
 
        // If n is a strong prime
        if (n > mean)
            return true;
        else
            return false;
    }
 
    // Driver code
    public static void main(String args[])
    {
 
        int n = 11;
 
        if (isStrongPrime(n))
            System.out.println("Yes");
 
        else
            System.out.println("No");
    }
}

Python3

# Python 3 program to check if given
# number is strong prime
from math import sqrt
 
# Utility function to check if a
# number is prime or not
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
     
    k = int(sqrt(n)) + 1
    for i in range(5, k, 6):
        if (n % i == 0 or n % (i + 2) == 0):
            return False
 
    return True
 
# Function that returns true if
# n is a strong prime
def isStrongPrime(n):
     
    # If n is not a prime number or
    # n is the first prime then return false
    if (isPrime(n) == False or n == 2):
        return False
 
    # Initialize previous_prime to n - 1
    # and next_prime to n + 1
    previous_prime = n - 1
    next_prime = n + 1
 
    # Find next prime number
    while (isPrime(next_prime) == False):
        next_prime += 1
 
    # Find previous prime number
    while (isPrime(previous_prime) == False):
        previous_prime -= 1
 
    # Arithmetic mean
    mean = (previous_prime + next_prime) / 2
 
    # If n is a strong prime
    if (n > mean):
        return True
    else:
        return False
 
# Driver code
if __name__ == '__main__':
    n = 11
 
    if (isStrongPrime(n)):
        print("Yes")
    else:
        print("No")
 
# This code is contributed by
# Sanjit_prasad

C#

// C# program to check if a given number is strong prime
using System;
class GFG {
 
    // Utility function to check
    // if a number is prime or not
    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 that returns true if n is a strong prime
    static bool isStrongPrime(int n)
    {
        // If n is not a prime number or
        // n is the first prime then return false
        if (!isPrime(n) || n == 2)
            return false;
 
        // Initialize previous_prime to n - 1
        // and next_prime to n + 1
        int previous_prime = n - 1;
        int next_prime = n + 1;
 
        // Find next prime number
        while (!isPrime(next_prime))
            next_prime++;
 
        // Find previous prime number
        while (!isPrime(previous_prime))
            previous_prime--;
 
        // Arithmetic mean
        int mean = (previous_prime + next_prime) / 2;
 
        // If n is a strong prime
        if (n > mean)
            return true;
        else
            return false;
    }
 
    // Driver code
    public static void Main()
    {
        int n = 11;
 
        if (isStrongPrime(n))
            Console.WriteLine("Yes");
        else
            Console.WriteLine("No");
    }
}

PHP

<?php
// PHP program to check if given number
// is strong isPrime
 
// Utility function to check if a
// number is prime or not
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 that returns true
// if n is a strong prime
function isStrongPrime($n)
{
    // If n is not a prime number or
    // n is the first prime then return false
    if (!isPrime($n) || $n == 2)
        return false;
 
    // Initialize previous_prime to n - 1
    // and next_prime to n + 1
    $previous_prime = $n - 1;
    $next_prime = $n + 1;
 
    // Find next prime number
    while (!isPrime($next_prime))
        $next_prime++;
 
    // Find previous prime number
    while (!isPrime($previous_prime))
        $previous_prime--;
 
    // Arithmetic mean
    $mean = ($previous_prime +
             $next_prime) / 2;
 
    // If n is a strong prime
    if ($n > $mean)
        return true;
    else
        return false;
}
 
// Driver code
$n = 11;
 
if (isStrongPrime($n))
    echo ("Yes");
else
    echo("No");
 
// This code is contributed
// by Shivi_Aggarwal
?>

Javascript

<script>
 
// Javascript program to check if
// given number is strong prime
 
// Utility function to check
// if a number is prime or not
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 that returns true if
// n is a strong prime
function isStrongPrime(n)
{
     
    // If n is not a prime number or
    // n is the first prime then return false
    if (!isPrime(n) || n == 2)
        return false;
 
    // Initialize previous_prime to n - 1
    // and next_prime to n + 1
    let previous_prime = n - 1;
    let next_prime = n + 1;
 
    // Find next prime number
    while (!isPrime(next_prime))
        next_prime++;
 
    // Find previous prime number
    while (!isPrime(previous_prime))
        previous_prime--;
 
    // Arithmetic mean
    let mean = parseInt((previous_prime +
                         next_prime) / 2);
 
    // If n is a strong prime
    if (n > mean)
        return true;
    else
        return false;
}
 
// Driver code
let n = 11;
 
if (isStrongPrime(n))
    document.write("Yes");
else
    document.write("No");
     
// This code is contributed by souravmahato348
 
</script>
Producción: 

Yes

 

Complejidad de tiempo: O (n 1/2 )

Espacio Auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por ihritik 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 *