Dado un entero positivo N , la tarea es verificar si el número dado es un buen primo o no. Si el número dado es bueno, imprima ‘ SÍ ‘. De lo contrario, escriba ‘ NO ‘.
Buen primo: en matemáticas, un buen primo es un número primo cuyo cuadrado es mayor que el producto de dos primos cualesquiera en el mismo número de posiciones antes y después de él en la secuencia de primos. En otras palabras, se dice que un primo Pn es un buen primo si
para cada 1 <= i < n.
Los primeros primos buenos son: 5, 11, 17, 29, 37, 41, 53, 59, 67, 71, 97, 101, 127, 149, 179, 191, 223, ….
Ejemplos:
Entrada: N = 5
Salida: SÍ
Explicación: 5 es un buen número primo
ya que 5^2 = 25 es mayor que 3,7 = 21
y 2,11 = 22.
Entrada: N = 20
Salida: NO
Acercarse:
1. Obtenga el número N.
2. Inicializar prev_prime = N-1 y next_prime = N+1
3. Repita el ciclo mientras prev_prime es mayor o igual a 2. Y verifique que tanto next_prime como prev_prime sean primos o no usen números primos.
4. Si ninguno de los dos es primo, repita los pasos 2 y 3.
5. Si tanto next_prime como prev_prime son primos, marque N^2 > next_prime . prev_prime o no.
- Si no, entonces el número no es bueno, imprima y detenga la ejecución y devuelva NO.
- En caso afirmativo, repita los pasos 2, 3, 4 y 5.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to check if a number
// is good prime or not
#include<bits/stdc++.h>
using namespace std;
// 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 loop
if (n % 2 == 0 || n % 3 == 0)
return false;
for(int i = 5; i * i <= n; i += 6)
{
if (n % i == 0 || n % (i + 2) == 0)
return false;
}
return true;
}
// Function to check if the
// given number is Good prime
bool isGoodprime (int n)
{
// Smallest good prime is 5
// So the number less than 5
// can not be a Good prime
if (n < 5)
return false;
int prev_prime = n - 1;
int next_prime = n + 1;
while (prev_prime >= 2)
{
// Calculate first prime number < n
while (!isPrime(prev_prime))
{
prev_prime--;
}
// Calculate first prime number > n
while (!isPrime(next_prime))
{
next_prime++;
}
// Check if product of next_prime
// and prev_prime is less than n^2
if ((prev_prime * next_prime) >= n * n)
return false;
prev_prime -= 1;
next_prime += 1;
}
return true;
}
// Driver code
int main()
{
int n = 11;
if (isGoodprime(n))
cout << "YES";
else
cout << "NO";
return 0;
}
// This code is contributed by himanshu77
Java
// Java program to check if a number is
// good prime or not
class GFG{
// 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 to check if the given
// number is good prime or not
static boolean isGoodrprime(int n)
{
// Smallest good prime is 5
// So the number less than 5
// can not be a good prime
if (n < 5)
return false;
int prev_prime = n - 1;
int next_prime = n + 1;
while (prev_prime >= 2)
{
// Calculate first prime number < n
while (!isPrime(prev_prime))
{
prev_prime--;
}
// Calculate first prime number > n
while (!isPrime(next_prime))
{
next_prime++;
}
// Check if product of next_prime
// and prev_prime
// is less than n^2
if ((prev_prime * next_prime) >= n * n)
return false;
prev_prime -= 1;
next_prime += 1;
}
return true;
}
// Driver code
public static void main(String []args)
{
int n = 11;
if (isGoodrprime(n))
System.out.println("YES");
else
System.out.println("NO");
}
}
// This code is contributed by amal kumar choubey
Python3
# Python3 program to check if a number is
# good prime or not
# 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
i = 5
while (i * i <= n):
if (n % i == 0 or n % (i + 2) == 0):
return False
i = i + 6
return True
# Function to check if the given number
# is good prime or not
def isGoodrPrime(n):
# Declaring variables as global
global next_prime, prev_prime
# Smallest good prime is 5
# So the number less than 5
# can not be a good prime
if(n < 5):
return False
# Initialize previous_prime to n - 1
# and next_prime to n + 1
prev_prime = n - 1
next_prime = n + 1
while(prev_prime >= 2):
# Calculate first prime number < n
while (not isPrime(prev_prime)):
prev_prime -= 1
# Calculate first prime number > n
while(not isPrime(next_prime)):
next_prime += 1
# Check if product of next_prime
# and prev_prime
# is less than n^2
if((prev_prime * next_prime) >= n * n):
return False
prev_prime -= 1
next_prime += 1
return True
# Driver code
if __name__ == '__main__':
n = 11
if(isGoodrPrime(n)):
print("Yes")
else:
print("No")
# This code is contributed by Shivam Singh
C#
// C# program to check if a number is
// good prime or not
using System;
class GFG {
// 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 to check
// if the given number is good prime or not
static bool isGoodrprime(int n)
{
// Smallest good prime is 5
// So the number less than 5
// can not be a good prime
if (n < 5)
return false;
int prev_prime = n - 1;
int next_prime = n + 1;
while (prev_prime >= 2) {
// Calculate first prime number < n
while (!isPrime(prev_prime)) {
prev_prime--;
}
// Calculate first prime number > n
while (!isPrime(next_prime)) {
next_prime++;
}
// check if product of next_prime
// and prev_prime
// is less than n^2
if ((prev_prime * next_prime)
>= n * n)
return false;
prev_prime -= 1;
next_prime += 1;
}
return true;
}
public static void Main()
{
int n = 11;
if (isGoodrprime(n))
Console.WriteLine("YES");
else
Console.WriteLine("NO");
}
}
Javascript
<script>
// Javascript program to check if a number
// is good prime or not
// 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 loop
if (n % 2 == 0 || n % 3 == 0)
return false;
for(let i = 5; i * i <= n; i += 6)
{
if (n % i == 0 || n % (i + 2) == 0)
return false;
}
return true;
}
// Function to check if the
// given number is Good prime
function isGoodprime (n)
{
// Smallest good prime is 5
// So the number less than 5
// can not be a Good prime
if (n < 5)
return false;
let prev_prime = n - 1;
let next_prime = n + 1;
while (prev_prime >= 2)
{
// Calculate first prime number < n
while (!isPrime(prev_prime))
{
prev_prime--;
}
// Calculate first prime number > n
while (!isPrime(next_prime))
{
next_prime++;
}
// Check if product of next_prime
// and prev_prime is less than n^2
if ((prev_prime * next_prime) >= n * n)
return false;
prev_prime -= 1;
next_prime += 1;
}
return true;
}
// Driver code
let n = 11;
if (isGoodprime(n))
document.write("YES");
else
document.write("NO");
// This code is contributed by Mayank Tyagi
</script>
Producción:
YES
Complejidad del tiempo: O(n 3/2 )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por SHUBHAMSINGH10 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA