Minimum absolute difference of a number and its closest prime
Given a positive integer N, the task is to find the absolute difference of N and the prime number closest to N .
Note: The closest prime to N can be either less than, equal to or greater than N.
Examples:
Input: N = 25
Output: 2
For N = 25
Closest prime greater than 25 is 29. So difference is 4.
Closest prime less than 25 is 23. So difference is 2.
The minimum of these two is 2.
Input: N = 2
Output: 0
As 2 itself is a prime number, closest prime number is 2. So difference is 0.
Approach:
- If N is prime then print 0.
- Else, find the first prime number > N and note its difference with N.
- Then, find the first prime number < N and note its difference with N.
- And print the minimum of these two differences obtained.
Below is the implementation of the above approach:
C++
// C++ program to find the minimum absolute // difference between a number and its closest prime #include <bits/stdc++.h> using namespace std; // Function to check if a number is prime or not bool isPrime( int N) { for ( int i = 2; i <= sqrt (N); i++) { if (N % i == 0) return false ; } return true ; } // Function to find the minimum absolute difference // between a number and its closest prime int getDifference( int N) { if (N == 0) return 2; else if (N == 1) return 1; else if (isPrime(N)) return 0; // Variables to store first prime // above and below N int aboveN = -1, belowN = -1; int n1; // Finding first prime number greater than N n1 = N + 1; while ( true ) { if (isPrime(n1)) { aboveN = n1; break ; } else n1++; } // Finding first prime number less than N n1 = N - 1; while ( true ) { if (isPrime(n1)) { belowN = n1; break ; } else n1--; } // Variables to store the differences int diff1 = aboveN - N; int diff2 = N - belowN; return min(diff1, diff2); } // Driver code int main() { int N = 25; cout << getDifference(N) << endl; return 0; // This code is contributed by Ryuga } |
Java
// Java program to find the minimum absolute // difference between a number and its closest prime class GFG { // Function to check if a number is prime or not static boolean isPrime( int N) { for ( int i = 2 ; i <= Math.sqrt(N); i++) { if (N % i == 0 ) return false ; } return true ; } // Function to find the minimum absolute difference // between a number and its closest prime static int getDifference( int N) { if (N == 0 ) return 2 ; else if (N == 1 ) return 1 ; else if (isPrime(N)) return 0 ; // Variables to store first prime // above and below N int aboveN = - 1 , belowN = - 1 ; int n1; // Finding first prime number greater than N n1 = N + 1 ; while ( true ) { if (isPrime(n1)) { aboveN = n1; break ; } else n1++; } // Finding first prime number less than N n1 = N - 1 ; while ( true ) { if (isPrime(n1)) { belowN = n1; break ; } else n1--; } // Variables to store the differences int diff1 = aboveN - N; int diff2 = N - belowN; return Math.min(diff1, diff2); } // Driver code public static void main(String args[]) { int N = 25 ; System.out.println(getDifference(N)); } } |
Python3
# Python 3 program to find the minimum # absolute difference between a number # and its closest prime from math import sqrt # Function to check if a number is # prime or not def isPrime(N): k = int (sqrt(N)) + 1 for i in range ( 2 , k, 1 ): if (N % i = = 0 ): return False return True # Function to find the minimum absolute # difference between a number and its # closest prime def getDifference(N): if (N = = 0 ): return 2 elif (N = = 1 ): return 1 elif (isPrime(N)): return 0 # Variables to store first prime # above and below N aboveN = - 1 belowN = - 1 # Finding first prime number # greater than N n1 = N + 1 while ( True ): if (isPrime(n1)): aboveN = n1 break else : n1 + = 1 # Finding first prime number # less than N n1 = N - 1 while ( True ): if (isPrime(n1)): belowN = n1 break else : n1 - = 1 # Variables to store the differences diff1 = aboveN - N diff2 = N - belowN return min (diff1, diff2) # Driver code if __name__ = = '__main__' : N = 25 print (getDifference(N)) # This code is contributed by # Surendra_Gangwar |
C#
// C# program to find the minimum absolute // difference between a number and its closest prime using System; class GFG { // Function to check if a number is prime or not static bool isPrime( int N) { for ( int i = 2; i <= Math.Sqrt(N); i++) { if (N % i == 0) return false ; } return true ; } // Function to find the minimum absolute difference // between a number and its closest prime static int getDifference( int N) { if (N == 0) return 2; else if (N == 1) return 1; else if (isPrime(N)) return 0; // Variables to store first prime // above and below N int aboveN = -1, belowN = -1; int n1; // Finding first prime number greater than N n1 = N + 1; while ( true ) { if (isPrime(n1)) { aboveN = n1; break ; } else n1++; } // Finding first prime number less than N n1 = N - 1; while ( true ) { if (isPrime(n1)) { belowN = n1; break ; } else n1--; } // Variables to store the differences int diff1 = aboveN - N; int diff2 = N - belowN; return Math.Min(diff1, diff2); } // Driver code public static void Main() { int N = 25; Console.WriteLine(getDifference(N)); } } // This code is contributed by anuj_67.. |
PHP
<?php // PHP program to find the minimum absolute // difference between a number and its // closest prime // Function to check if a number // is prime or not function isPrime( $N ) { for ( $i = 2; $i <= sqrt( $N ); $i ++) { if ( $N % $i == 0) return false; } return true; } // Function to find the minimum absolute difference // between a number and its closest prime function getDifference( $N ) { if ( $N == 0) return 2; else if ( $N == 1) return 1; else if (isPrime( $N )) return 0; // Variables to store first prime // above and below N $aboveN = -1; $belowN = -1; // Finding first prime number greater than N $n1 = $N + 1; while (true) { if (isPrime( $n1 )) { $aboveN = $n1 ; break ; } else $n1 ++; } // Finding first prime number less than N $n1 = $N - 1; while (true) { if (isPrime( $n1 )) { $belowN = $n1 ; break ; } else $n1 --; } // Variables to store the differences $diff1 = $aboveN - $N ; $diff2 = $N - $belowN ; return min( $diff1 , $diff2 ); } // Driver code $N = 25; echo getDifference( $N ) . "\n" ; // This code is contributed // by Akanksha Rai |
Javascript
// Javascript program to find the minimum absolute // difference between a number and its // closest prime // Function to check if a number // is prime or not function isPrime(N) { for (let i = 2; i <= Math.sqrt(N); i++) { if (N % i == 0) return false ; } return true ; } // Function to find the minimum absolute difference // between a number and its closest prime function getDifference(N) { if (N == 0) return 2; else if (N == 1) return 1; else if (isPrime(N)) return 0; // Variables to store first prime // above and below N let aboveN = -1; let belowN = -1; // Finding first prime number greater than N let n1 = N + 1; while ( true ) { if (isPrime(n1)) { aboveN = n1; break ; } else n1++; } // Finding first prime number less than N n1 = N - 1; while ( true ) { if (isPrime(n1)) { belowN = n1; break ; } else n1--; } // Variables to store the differences let diff1 = aboveN - N; let diff2 = N - belowN; return Math.min(diff1, diff2); } // Driver code let N = 25; document.write(getDifference(N) + "<br>" ); // This code is contributed // by gfgking |
Output:
2
Time Complexity: O(N*sqrt(N)), where N represents the given integer.
Auxiliary Space: O(1), no extra space is required, so it is a constant.