Given two squares with side lengths 
and 
(a > b). The task is to check if difference of their areas is prime or not. Here side length could be large ( 1 < b < a < 1012).
Examples:
Input : a = 6, b = 5 Output : Yes Input : a = 61690850361, b = 24777622630 Output : No
Approach: Since the sides are and . Therefore, difference of their areas = (a2 – b2), which can be expressed as (a – b)(a + b) . This is prime if and only if a – b = 1 and a + b is a prime . Since a+b is at most 2×1012, we can use trial division to check its primality.
Below is the implementation of the above idea:
C++
// C++ program to check if difference of// areas of two squares is prime or not// when side length is large#include <bits/stdc++.h>using namespace std;// Function to check if number is primebool isPrime(long long 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 (long long 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 difference of areas of// square is primebool isDiffPrime(long long int a, long long int b){ // when a+b is prime and a-b is 1 if (isPrime(a + b) && a - b == 1) return true; else return false;}// Driver codeint main(){ long long int a = 6, b = 5; if (isDiffPrime(a, b)) cout << "Yes"; else cout << "No"; return 0;} |
Java
// Java program to check if difference// of areas of two squares is prime or // not when side length is largeclass GFG{ // Function to check if number // is primestatic boolean isPrime(long 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 (long i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false; return true;}// Function to check if difference // of areas of square is primestatic boolean isDiffPrime(long a, long b){ // when a+b is prime and a-b is 1 if (isPrime(a + b) && a - b == 1) return true; else return false;}// Driver codepublic static void main(String []args){ long a = 6, b = 5; if (isDiffPrime(a, b)) System.out.println("Yes"); else System.out.println("No");}}// This code is contributed by ihritik |
C#
// C# program to check if difference// of areas of two squares is prime // or not when side length is largeusing System;class GFG{// Function to check if number// is primestatic bool isPrime(long 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 (long i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false; return true;}// Function to check if difference // of areas of square is primestatic bool isDiffPrime(long a, long b){ // when a+b is prime and a-b is 1 if (isPrime(a + b) && a - b == 1) return true; else return false;}// Driver codepublic static void Main(){ long a = 6, b = 5; if (isDiffPrime(a, b)) Console.WriteLine("Yes"); else Console.WriteLine("No");}}// This code is contributed by ihritik |
Python3
# Python3 program to check if # difference of areas of two # squares is prime or not when# side length is largedef 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 difference # of areas of square is primedef isDiffPrime(a, b): # when a+b is prime and a-b is 1 if (isPrime(a + b) and a - b == 1): return True else: return False# Driver codea = 6b = 5if (isDiffPrime(a, b)): print("Yes")else: print("No")# This code is contributed by ihritik |
PHP
<?php// PHP program to check if difference // of areas of two squares is prime // or not when side length is largefunction 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($i = 5; $i * $i <= $n; $i = $i + 6) if ($n % $i == 0 || $n % ($i + 2) == 0) return false; return true; } // Function to check if difference// of areas of square is primefunction isDiffPrime($a, $b){ # when a+b is prime and a-b is 1 if (isPrime($a + $b) && $a - $b == 1) return true; else return false;}// Driver code$a = 6;$b = 5;if (isDiffPrime($a, $b)) echo "Yes";else echo "No";// This code is contributed by ihritik?> |
Javascript
<script>// Javascript program to check if difference// of areas of two squares is prime// or not when side length is largefunction 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(let i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false; return true;}// Function to check if difference// of areas of square is primefunction isDiffPrime(a, b){ // when a+b is prime and a-b is 1 if (isPrime(a + b) && a - b == 1) return true; else return false;}// Driver codelet a = 6;let b = 5;if (isDiffPrime(a, b)) document.write("Yes");else document.write("No");// This code is contributed by Saurabh Jaiswal</script> |
Output:
Yes
Time Complexity: O(sqrtn)
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!
