Comprueba n^2 – m^2 es primo o no

Dados dos enteros n y m. Compruebe n ^ 2: m ^ 2 es primo o no. n y m pueden ser muy grandes. 

Ejemplos: 

Input : n = 6, m = 5
Output : YES

Input : n = 16, m = 13
Output : NO

Una solución simple es calcular primero n ^ 2 – m ^ 2, luego verificar si es primo o no. n^2: m^2 puede ser muy grande, es posible que ni siquiera quepa en un entero de 64 bits. La verificación de la primalidad ciertamente no se puede realizar de manera ingenua.

Una mejor solución es expresar n^2 – m^2 como (nm)(n+m). Esto es primo si y solo si nm = 1 y n+m es primo. 

// CPP program to find n^2 - m^2
// is prime or not.
#include <bits/stdc++.h>
using namespace std;
 
// Check a number is prime or not
bool isprime(int x)
{
    // run a loop upto square of given number
    for (int i = 2; i * i <= x; i++)
        if (x % i == 0)
            return false;
    return true;
}
 
// Check if n^2 - m^2 is prime
bool isNSqMinusnMSqPrime(int m, int n)
{
    if (n - m == 1 and isprime(m + n))
        return true;
    else
        return false;
}
 
// Driver code
int main()
{
    int m = 13, n = 16;
    if (isNSqMinusnMSqPrime(m, n))
        cout << "YES";
    else
        cout << "NO";
 
    return 0;
}

// C program to find n^2 - m^2
// is prime or not.
#include <stdio.h>
 
// Check a number is prime or not
int isprime(int x)
{
   
    // run a loop upto square of given number
    for (int i = 2; i * i <= x; i++)
        if (x % i == 0)
            return 0;
    return 1;
}
  
// Check if n^2 - m^2 is prime
int isNSqMinusnMSqPrime(int m, int n)
{
    if (n - m == 1 && isprime(m + n))
        return 1;
    else
        return 0;
}
  
// Driver code
int main()
{
    int m = 13, n = 16;
    if (isNSqMinusnMSqPrime(m, n))
        printf("YES");
    else
        printf("NO");
    return 0;
}

// Java program to find n^2 - m^2
// is prime or not.
 
class GFG
{
        // Check if a number is prime or not
        static boolean isprime(int x)
        {
            // run a loop upto square of given number
            for (int i = 2; i * i <= x; i++)
                if (x % i == 0)
                    return false;
            return true;
        }
         
        // Check if n^2 - m^2 is prime
        static boolean isNSqMinusnMSqPrime(int m, int n)
        {
            if (n - m == 1 && isprime(m + n))
                return true;
            else
                return false;
        }
         
        // Driver code
        public static void  main(String [] args)
        {
            int m = 13, n = 16;
            if (isNSqMinusnMSqPrime(m, n))
                System.out.println("YES");
            else
                System.out.println("NO");
         
        }
}
 
// This code is contributed
// by ihritik

# Python program to find n^2 - m^2
# is prime or not.
 
# Check a number is prime or not
def isprime(x):
 
    # run a loop upto square
    # of given number
    for i in range(2, math.sqrt(x)):
        if (x % i == 0) :
            return False;
    return True;
 
# Check if n^2 - m^2 is prime
def isNSqMinusnMSqPrime( m, n):
 
    if (n - m == 1 and isprime(m + n)):
        return True;
    else:
        return False;
 
# Driver code
m = 13;
n = 16;
if (isNSqMinusnMSqPrime(m, n)) :
    print ( "YES");
else:
    print ("NO");
 
# This code is contributed
# by Shivi_Aggarwal

// C# program to find n^2 - m^2
// is prime or not.
using System;
 
class GFG
{
// Check if a number is prime or not
static bool isprime(int x)
{
    // run a loop upto square
    // of given number
    for (int i = 2; i * i <= x; i++)
        if (x % i == 0)
            return false;
    return true;
}
 
// Check if n^2 - m^2 is prime
static bool isNSqMinusnMSqPrime(int m,
                                int n)
{
    if (n - m == 1 && isprime(m + n))
        return true;
    else
        return false;
}
 
// Driver code
public static void Main()
{
    int m = 13, n = 16;
    if (isNSqMinusnMSqPrime(m, n))
        Console.Write("YES");
    else
        Console.Write("NO");
}
}
 
// This code is contributed
// by Smitha

<?php
//PHP program to find n^2 - m^2
// is prime or not.
 
// Check a number is prime or not
function isprime($x)
{
    // run a loop upto square
    // of given number
    for ( $i = 2; $i * $i <= $x; $i++)
        if ($x % i == 0)
            return false;
    return true;
}
 
// Check if n^2 - m^2 is prime
function isNSqMinusnMSqPrime($m, $n)
{
    if ($n - $m == 1 and isprime($m + $n))
        return true;
    else
        return false;
}
 
// Driver code
$m = 13; $n = 16;
if (isNSqMinusnMSqPrime($m, $n))
    echo "YES";
else
    echo "NO";
     
// This code is contributed
// by inder_verma
?>

<script>
 
// JavaScript program to find n^2 - m^2
// is prime or not.
 
// Check if a number is prime or not
function isprime(x)
{
     
    // Run a loop upto square of given number
    for(var i = 2; i * i <= x; i++)
        if (x % i == 0)
            return false;
             
    return true;
}
 
// Check if n^2 - m^2 is prime
function isNSqMinusnMSqPrime(m, n)
{
    if (n - m == 1 && isprime(m + n))
        return true;
    else
        return false;
}
         
// Driver Code
var m = 13, n = 16;
 
if (isNSqMinusnMSqPrime(m, n))
    document.write("YES");
else
    document.write("NO");
 
// This code is contributed by Khushboogoyal499
 
</script>

Producción:  

NO

Complejidad del tiempo: O(sqrt(n+m))