Gegeben seien zwei ganze Zahlen n und m. Überprüfen Sie n^2 – m^2 ist eine Primzahl oder nicht. n und m können sehr groß werden. 

Beispiele: 

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

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

Eine einfache Lösung besteht darin, zuerst n^2 – m^2 zu berechnen und dann zu prüfen, ob es eine Primzahl ist oder nicht. n ^ 2 – m ^ 2 kann sehr groß sein – es passt möglicherweise nicht einmal in eine 64-Bit-Ganzzahl. Die Überprüfung der Primzahl darauf kann sicherlich nicht naiv durchgeführt werden.

Eine bessere Lösung ist es, n^2 – m^2 als (nm)(n+m) auszudrücken. Dies ist genau dann eine Primzahl, wenn nm = 1 und n+m eine Primzahl ist. 

// 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;
}

// 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>

Ausgabe:  

NO

Zeitkomplexität: O(sqrt(n+m))
 

Falls Sie an Live-Kursen mit Experten teilnehmen möchten , beziehen Sie sich bitte auf DSA Live-Kurse für Berufstätige und Competitive Programming Live for Students .