Comprueba si el número dado es primo de Wagstaff o no

Posted on by Rudeus Greyrat

Dado un entero positivo n, la tarea es verificar si es un primo de Wagstaff o no. Escriba ‘SÍ’ si el número dado es primo de Wagstaff; de lo contrario, escriba ‘NO’.
Wagstaff primo : En matemáticas, Wagstaff primo es un número primo ‘n’ de la forma  n = \frac{2^{q} + 1}{3}
donde ‘q’ es un primo impar.
Primero, algunos números primos de Wagstaff son: 

3, 11, 43, 683, 2731, 43691, 174763, 2796203……….

Ejemplos:  

Input: 43
Output: Yes
43 can be expressed as - (27 + 1 )/ 3

Input: 31
Output: No
31 can not be expressed in above mentioned form.

Acercarse:  

  1. Comprueba primero si el número dado es un número primo o no. Para verificar que un número sea primo, consulte este .
  2. Luego verifica si se puede expresar en la forma de (n * 3 – 1) y debe ser una potencia de 2. Para verificar que un número sea una potencia de 2, consulta esto.
  3. Si ambas condiciones son verdaderas, entonces el número es un número primo de Wagstaff. Por lo tanto, escriba «SÍ». De lo contrario, escriba «NO»

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

C++

// CPP program to check if a number is
// Wagstaff 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 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;
}
 
// Utility function to check power of two
bool isPowerOfTwo(int n)
{
    return (n && !(n & (n - 1)));
}
 
// Driver Program
int main()
{
    int n = 43;
 
    // Check if number is prime
    // and of the form (2^q +1 )/ 3
 
    if (isPrime(n) && (isPowerOfTwo(n * 3 - 1))) {
        cout << "YES\n";
    }
    else {
        cout << "NO\n";
    }
 
    return 0;
}

Java

// JAVA program to check if a number is
// Wagstaff 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;
    }
 
    // Utility function to check power of two
    static boolean isPowerOfTwo(int n)
    {
        return n != 0 && ((n & (n - 1)) == 0);
    }
 
    // Driver Program
    public static void main(String[] args)
    {
        int n = 43;
 
        // Check if number is prime
        // and of the form ( 2^q +1 )/3
        if (isPrime(n) && (isPowerOfTwo(n * 3 - 1))) {
            System.out.println("YES");
        }
        else {
            System.out.println("NO");
        }
    }
}

Python3

# Python 3 program to check if a number is 
# Wagstaff 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
 
# Utility function to Check
# power of two
 
def isPowerOfTwo(n):
     
    return (n and (not(n & (n - 1))))
           
# Driver Code 
n = 43
       
# Check if number is prime 
# and of the form ( 2 ^ q + 1 ) / 3
   
if(isPrime(n) and isPowerOfTwo(n * 3-1)):
   
    print("YES")
   
else:
   
    print("NO")

C#

// C# program to check if a number
// is Wagstaff 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;
}
 
// Utility function to
// check power of two
static bool isPowerOfTwo(int n)
{
    return n != 0 && ((n & (n - 1)) == 0);
}
 
// Driver Code
public static void Main()
{
    int n = 43;
 
    // Check if number is prime
    // and of the form ( 2^q +1 )/3
    if (isPrime(n) &&
       (isPowerOfTwo(n * 3 - 1)))
    {
        Console.WriteLine("YES");
    }
    else
    {
        Console.WriteLine("NO");
    }
}
}
 
// This code is contributed
// by inder_verma

PHP

<?php
// PHP program to check if a number
// is Wagstaff 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 below loop
    if ($n % 2 == 0 or $n % 3 == 0)
        return false;
 
    for ($i = 5;
         $i * $i <= $n; $i = $i + 6)
    {
        if ($n % $i == 0 or
            $n % ($i + 2) == 0)
        {
            return false;
        }
    }
 
    return true;
}
 
// Utility function to
// check power of two
function isPowerOfTwo($n)
{
    return ($n && !($n & ($n - 1)));
}
 
// Driver Code
$n = 43;
 
// Check if number is prime
// and of the form (2^q +1 )/ 3
 
if (isPrime($n) &&
   (isPowerOfTwo($n * 3 - 1)))
{
    echo "YES";
}
else
{
    echo"NO";
}
 
// This code is contributed
// by Shashank
?>

Javascript

<script>
 
// JavaScript program to check if a number is
// Wagstaff 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 below loop
        if (n % 2 == 0 || n % 3 == 0)
            return false;
 
        for (var i = 5; i * i <= n; i = i + 6) {
            if (n % i == 0 || n % (i + 2) == 0) {
                return false;
            }
        }
        return true;
    }
 
    // Utility function to check power of two
    function isPowerOfTwo(n)
    {
        return (n != 0 )&& ((n & (n - 1)) == 0);
    }
 
// Driver Program
        
     var n = 43;
 
        // Check if number is prime
        // and of the form ( 2^q +1 )/3
        if (isPrime(n) && (isPowerOfTwo(n * 3 - 1))) {
            document.write("YES");
        }
        else {
            document.write("NO");
        }
 
</script>
Producción: 

YES

 

Complejidad del 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 *