Given two integers n and m. Check n^2 – m^2 is prime or not. n and m can be very large.
Examples:
Input : n = 6, m = 5
Output : YES
Input : n = 16, m = 13
Output : NO
A simple solution is to first compute n^2 – m^2, then check if it is prime or not. n^2 – m^2 might be very large – it might not even fit into 64-bit integer. Checking primality for it certainly cannot be performed naively.
A better solution is to express n^2 – m^2 as (n-m)(n+m). This is prime if and only if n-m = 1 and n+m is a prime.
C++
// 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 notbool 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 primebool isNSqMinusnMSqPrime(int m, int n){ if (n - m == 1 and isprime(m + n)) return true; else return false;}// Driver codeint main(){ int m = 13, n = 16; if (isNSqMinusnMSqPrime(m, n)) cout << "YES"; else cout << "NO"; return 0;} |
C
// C program to find n^2 - m^2// is prime or not.#include <stdio.h>// Check a number is prime or notint 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 primeint isNSqMinusnMSqPrime(int m, int n){ if (n - m == 1 && isprime(m + n)) return 1; else return 0;} // Driver codeint main(){ int m = 13, n = 16; if (isNSqMinusnMSqPrime(m, n)) printf("YES"); else printf("NO"); return 0;} |
Java
// 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 |
Python3
# 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#
// 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 |
Javascript
<script>// JavaScript program to find n^2 - m^2// is prime or not.// Check if a number is prime or notfunction 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 primefunction isNSqMinusnMSqPrime(m, n){ if (n - m == 1 && isprime(m + n)) return true; else return false;} // Driver Codevar m = 13, n = 16;if (isNSqMinusnMSqPrime(m, n)) document.write("YES");else document.write("NO");// This code is contributed by Khushboogoyal499</script> |
PHP
<?php//PHP program to find n^2 - m^2// is prime or not.// Check a number is prime or notfunction 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 primefunction 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?> |
Output
NO
Time Complexity: O(sqrt(n+m))
Auxiliary Space: O(1)
Approach:
The approach is to use a property of prime numbers which states that if a number p is prime, then p^2 – 1 is divisible by 24. So, if n^2 – m^2 is prime, then it should satisfy this property as well.
We can check if n^2 – m^2 is divisible by 24 or not. If it is, then it can be a prime number, otherwise, it is definitely not a prime number.
So, in the code, we first calculate n^2 – m^2 and then check if it is less than or equal to 1. If it is, then it is not a prime number. Otherwise, we check if it is divisible by 24 by checking if (n^2 – m^2 + 1) is divisible by 24 or not. If it is, then we return true, else we return false.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;// Check if n^2 - m^2 is primebool isNSqMinusnMSqPrime(int m, int n){ int num = n*n - m*m; if (num <= 1) return false; // Check if p^2 - 1 is divisible by 24 if ((num+1)%24 == 0) return true; return false;}// Driver codeint main(){ int m = 13, n = 16; if (isNSqMinusnMSqPrime(m, n)) cout << "YES"; else cout << "NO"; return 0;} |
Java
import java.util.*;publicclass Main { // Check if n^2 - m^2 is prime static boolean isNSqMinusnMSqPrime(int m, int n) { int num = n * n - m * m; if (num <= 1) return false; // Check if p^2 - 1 is divisible by 24 if ((num + 1) % 24 == 0) return true; return false; } // Driver codepublic 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 Prajwal Kandekar |
Python3
# Check if n^2 - m^2 is primedef isNSqMinusnMSqPrime(m, n): num = n*n - m*m if num <= 1: return False # Check if p^2 - 1 is divisible by 24 if (num+1) % 24 == 0: return True return False# Driver codeif __name__ == '__main__': m, n = 13, 16 if isNSqMinusnMSqPrime(m, n): print("YES") else: print("NO") |
C#
using System;class Program{ // Check if n^2 - m^2 is prime static bool IsNSqMinusnMSqPrime(int m, int n) { int num = n * n - m * m; if (num <= 1) return false; // Check if p^2 - 1 is divisible by 24 if ((num + 1) % 24 == 0) return true; return false; } // Driver code static void Main() { int m = 13, n = 16; if (IsNSqMinusnMSqPrime(m, n)) Console.WriteLine("YES"); else Console.WriteLine("NO"); }} |
Javascript
function isNSqMinusnMSqPrime(m, n) {var num = n * n - m * m;if (num <= 1) {return false;}// Check if p^2 - 1 is divisible by 24if ((num + 1) % 24 == 0) {return true;}return false;}// Driver codevar m = 13,n = 16;if (isNSqMinusnMSqPrime(m, n)) {console.log("YES");} else {console.log("NO");} |
Output
NO
Time Complexity: O(1)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!