// C++ program for the above approach #include    using namespace std; // Function to return nearest prime number int prime(int n) {  // All prime numbers are odd except two  if (n & 1)  n -= 2;  else  n--;  int i j;  for (i = n; i >= 2; i -= 2) {  if (i % 2 == 0)  continue;  for (j = 3; j <= sqrt(i); j += 2) {  if (i % j == 0)  break;  }  if (j > sqrt(i))  return i;  }  // It will only be executed when n is 3  return 2; } // Driver Code int main() {  int n = 17;  cout << prime(n);  return 0; } 

// C program for the above approach #include  #include  // Function to return nearest prime number int prime(int n) {  // All prime numbers are odd except two  if (n & 1)  n -= 2;  else  n--;  int i j;  for (i = n; i >= 2; i -= 2) {  if (i % 2 == 0)  continue;  for (j = 3; j <= sqrt(i); j += 2) {  if (i % j == 0)  break;  }  if (j > sqrt(i))  return i;  }  // It will only be executed when n is 3  return 2; } // Driver Code int main() {  int n = 17;  printf('%d' prime(n));  return 0; } // This code is contributed by Sania Kumari Gupta 

// Java program for the above approach import java.io.*; class GFG {  // Function to return nearest prime number  static int prime(int n)  {  // All prime numbers are odd except two  if (n % 2 != 0)  n -= 2;  else  n--;  int i j;  for (i = n; i >= 2; i -= 2) {  if (i % 2 == 0)  continue;  for (j = 3; j <= Math.sqrt(i); j += 2) {  if (i % j == 0)  break;  }  if (j > Math.sqrt(i))  return i;  }  // It will only be executed when n is 3  return 2;  }  // Driver Code  public static void main(String[] args)  {  int n = 17;  System.out.print(prime(n));  } } // This code is contributed by subham348. 

# Python program for the above approach # Function to return nearest prime number from math import floor sqrt def prime(n): # All prime numbers are odd except two if (n & 1): n -= 2 else: n -= 1 ij = 03 for i in range(n 2 -2): if(i % 2 == 0): continue while(j <= floor(sqrt(i)) + 1): if (i % j == 0): break j += 2 if (j > floor(sqrt(i))): return i # It will only be executed when n is 3 return 2 # Driver Code n = 17 print(prime(n)) # This code is contributed by shinjanpatra 

// C# program for the above approach using System; class GFG {  // Function to return nearest prime number  static int prime(int n)  {  // All prime numbers are odd except two  if (n % 2 != 0)  n -= 2;  else  n--;  int i j;  for (i = n; i >= 2; i -= 2) {  if (i % 2 == 0)  continue;  for (j = 3; j <= Math.Sqrt(i); j += 2) {  if (i % j == 0)  break;  }  if (j > Math.Sqrt(i))  return i;  }  // It will only be executed when n is 3  return 2;  }  // Driver Code  public static void Main()  {  int n = 17;  Console.Write(prime(n));  } } // This code is contributed by subham348. 

<script> // Javascript program for the above approach // Function to return nearest prime number function prime(n) {    // All prime numbers are odd except two  if (n & 1)  n -= 2;  else  n--;  let i j;  for(i = n; i >= 2; i -= 2)   {  if (i % 2 == 0)  continue;  for(j = 3; j <= Math.sqrt(i); j += 2)   {  if (i % j == 0)  break;  }  if (j > Math.sqrt(i))  return i;  }  // It will only be executed when n is 3  return 2; } // Driver Code let n = 17; document.write(prime(n)); // This code is contributed by souravmahato348 </script> 

// C++ program to find the nearest prime to n. #include   #define MAX 1000000 using namespace std; // array to store all primes less than 10^6 vector<int> primes; // Utility function of Sieve of Sundaram void Sieve() {  int n = MAX;  // In general Sieve of Sundaram produces primes  // smaller than (2*x + 2) for a number given  // number x  int nNew = sqrt(n);  // This array is used to separate numbers of the  // form i+j+2ij from others where 1 <= i <= j  int marked[n/2+500] = {0};  // eliminate indexes which does not produce primes  for (int i=1; i<=(nNew-1)/2; i++)  for (int j=(i*(i+1))<<1; j<=n/2; j=j+2*i+1)  marked[j] = 1;  // Since 2 is a prime number  primes.push_back(2);  // Remaining primes are of the form 2*i + 1 such  // that marked[i] is false.  for (int i=1; i<=n/2; i++)  if (marked[i] == 0)  primes.push_back(2*i + 1); } // modified binary search to find nearest prime less than N int binarySearch(int leftint rightint n) {  if (left<=right)  {  int mid = (left + right)/2;  // base condition is if we are reaching at left  // corner or right corner of primes[] array then  // return that corner element because before or  // after that we don't have any prime number in  // primes array  if (mid == 0 || mid == primes.size()-1)  return primes[mid];  // now if n is itself a prime so it will be present  // in primes array and here we have to find nearest  // prime less than n so we will return primes[mid-1]  if (primes[mid] == n)  return primes[mid-1];  // now if primes[mid]n that  // mean we reached at nearest prime  if (primes[mid] < n && primes[mid+1] > n)  return primes[mid];  if (n < primes[mid])  return binarySearch(left mid-1 n);  else  return binarySearch(mid+1 right n);  }  return 0; } // Driver program to run the case int main() {  Sieve();  int n = 17;  cout << binarySearch(0 primes.size()-1 n);  return 0; } 

// Java program to find the nearest prime to n. import java.util.*; class GFG {   static int MAX=1000000; // array to store all primes less than 10^6 static ArrayList<Integer> primes = new ArrayList<Integer>(); // Utility function of Sieve of Sundaram static void Sieve() {  int n = MAX;  // In general Sieve of Sundaram produces primes  // smaller than (2*x + 2) for a number given  // number x  int nNew = (int)Math.sqrt(n);  // This array is used to separate numbers of the  // form i+j+2ij from others where 1 <= i <= j  int[] marked = new int[n / 2 + 500];  // eliminate indexes which does not produce primes  for (int i = 1; i <= (nNew - 1) / 2; i++)  for (int j = (i * (i + 1)) << 1;   j <= n / 2; j = j + 2 * i + 1)  marked[j] = 1;  // Since 2 is a prime number  primes.add(2);  // Remaining primes are of the form 2*i + 1 such  // that marked[i] is false.  for (int i = 1; i <= n / 2; i++)  if (marked[i] == 0)  primes.add(2 * i + 1); } // modified binary search to find nearest prime less than N static int binarySearch(int leftint rightint n) {  if (left <= right)  {  int mid = (left + right) / 2;  // base condition is if we are reaching at left  // corner or right corner of primes[] array then  // return that corner element because before or  // after that we don't have any prime number in  // primes array  if (mid == 0 || mid == primes.size() - 1)  return primes.get(mid);  // now if n is itself a prime so it will be present  // in primes array and here we have to find nearest  // prime less than n so we will return primes[mid-1]  if (primes.get(mid) == n)  return primes.get(mid - 1);  // now if primes[mid]n that  // mean we reached at nearest prime  if (primes.get(mid) < n && primes.get(mid + 1) > n)  return primes.get(mid);  if (n < primes.get(mid))  return binarySearch(left mid - 1 n);  else  return binarySearch(mid + 1 right n);  }  return 0; } // Driver code public static void main (String[] args)  {  Sieve();  int n = 17;  System.out.println(binarySearch(0  primes.size() - 1 n)); } } // This code is contributed by mits 

# Python3 program to find the nearest # prime to n. import math MAX = 10000; # array to store all primes less # than 10^6 primes = []; # Utility function of Sieve of Sundaram def Sieve(): n = MAX; # In general Sieve of Sundaram produces # primes smaller than (2*x + 2) for a  # number given number x nNew = int(math.sqrt(n)); # This array is used to separate numbers # of the form i+j+2ij from others where  # 1 <= i <= j marked = [0] * (int(n / 2 + 500)); # eliminate indexes which does not # produce primes for i in range(1 int((nNew - 1) / 2) + 1): for j in range(((i * (i + 1)) << 1) (int(n / 2) + 1) (2 * i + 1)): marked[j] = 1; # Since 2 is a prime number primes.append(2); # Remaining primes are of the form  # 2*i + 1 such that marked[i] is false. for i in range(1 int(n / 2) + 1): if (marked[i] == 0): primes.append(2 * i + 1); # modified binary search to find nearest # prime less than N def binarySearch(left right n): if (left <= right): mid = int((left + right) / 2); # base condition is if we are reaching  # at left corner or right corner of  # primes[] array then return that corner  # element because before or after that  # we don't have any prime number in # primes array if (mid == 0 or mid == len(primes) - 1): return primes[mid]; # now if n is itself a prime so it will  # be present in primes array and here # we have to find nearest prime less than # n so we will return primes[mid-1] if (primes[mid] == n): return primes[mid - 1]; # now if primes[mid]n  # that means we reached at nearest prime if (primes[mid] < n and primes[mid + 1] > n): return primes[mid]; if (n < primes[mid]): return binarySearch(left mid - 1 n); else: return binarySearch(mid + 1 right n); return 0; # Driver Code Sieve(); n = 17; print(binarySearch(0 len(primes) - 1 n)); # This code is contributed by chandan_jnu 

// C# program to find the nearest prime to n. using System; using System.Collections; class GFG {   static int MAX = 1000000; // array to store all primes less than 10^6 static ArrayList primes = new ArrayList(); // Utility function of Sieve of Sundaram static void Sieve() {  int n = MAX;  // In general Sieve of Sundaram produces   // primes smaller than (2*x + 2) for a   // number given number x  int nNew = (int)Math.Sqrt(n);  // This array is used to separate numbers of the  // form i+j+2ij from others where 1 <= i <= j  int[] marked = new int[n / 2 + 500];  // eliminate indexes which does not produce primes  for (int i = 1; i <= (nNew - 1) / 2; i++)  for (int j = (i * (i + 1)) << 1;   j <= n / 2; j = j + 2 * i + 1)  marked[j] = 1;  // Since 2 is a prime number  primes.Add(2);  // Remaining primes are of the form 2*i + 1   // such that marked[i] is false.  for (int i = 1; i <= n / 2; i++)  if (marked[i] == 0)  primes.Add(2 * i + 1); } // modified binary search to find  // nearest prime less than N static int binarySearch(int left int right int n) {  if (left <= right)  {  int mid = (left + right) / 2;  // base condition is if we are reaching at left  // corner or right corner of primes[] array then  // return that corner element because before or  // after that we don't have any prime number in  // primes array  if (mid == 0 || mid == primes.Count - 1)  return (int)primes[mid];  // now if n is itself a prime so it will be   // present in primes array and here we have   // to find nearest prime less than n so we  // will return primes[mid-1]  if ((int)primes[mid] == n)  return (int)primes[mid - 1];  // now if primes[mid]n   // that mean we reached at nearest prime  if ((int)primes[mid] < n &&  (int)primes[mid + 1] > n)  return (int)primes[mid];  if (n < (int)primes[mid])  return binarySearch(left mid - 1 n);  else  return binarySearch(mid + 1 right n);  }  return 0; } // Driver code static void Main()  {  Sieve();  int n = 17;  Console.WriteLine(binarySearch(0  primes.Count - 1 n)); } } // This code is contributed by chandan_jnu 

 // PHP program to find the nearest // prime to n. $MAX = 10000; // array to store all primes less // than 10^6 $primes = array(); // Utility function of Sieve of Sundaram function Sieve() { global $MAX $primes; $n = $MAX; // In general Sieve of Sundaram produces // primes smaller than (2*x + 2) for a  // number given number x $nNew = (int)(sqrt($n)); // This array is used to separate numbers // of the form i+j+2ij from others where  // 1 <= i <= j $marked = array_fill(0 (int)($n / 2 + 500) 0); // eliminate indexes which does not // produce primes for ($i = 1; $i <= ($nNew - 1) / 2; $i++) for ($j = ($i * ($i + 1)) << 1; $j <= $n / 2; $j = $j + 2 * $i + 1) $marked[$j] = 1; // Since 2 is a prime number array_push($primes 2); // Remaining primes are of the form  // 2*i + 1 such that marked[i] is false. for ($i = 1; $i <= $n / 2; $i++) if ($marked[$i] == 0) array_push($primes 2 * $i + 1); } // modified binary search to find nearest // prime less than N function binarySearch($left $right $n) { global $primes; if ($left <= $right) { $mid = (int)(($left + $right) / 2); // base condition is if we are reaching  // at left corner or right corner of  // primes[] array then return that corner  // element because before or after that  // we don't have any prime number in // primes array if ($mid == 0 || $mid == count($primes) - 1) return $primes[$mid]; // now if n is itself a prime so it will  // be present in primes array and here // we have to find nearest prime less than // n so we will return primes[mid-1] if ($primes[$mid] == $n) return $primes[$mid - 1]; // now if primes[mid]n  // that means we reached at nearest prime if ($primes[$mid] < $n && $primes[$mid + 1] > $n) return $primes[$mid]; if ($n < $primes[$mid]) return binarySearch($left $mid - 1 $n); else return binarySearch($mid + 1 $right $n); } return 0; } // Driver Code Sieve(); $n = 17; echo binarySearch(0 count($primes) - 1 $n); // This code is contributed by chandan_jnu ?> 

 <script>  // JavaScript program to find the nearest prime to n.  // array to store all primes less than 10^6  var primes = [];  // Utility function of Sieve of Sundaram  var MAX = 1000000;  function Sieve()   {  let n = MAX;  // In general Sieve of Sundaram produces primes  // smaller than (2*x + 2) for a number given  // number x  let nNew = parseInt(Math.sqrt(n));  // This array is used to separate numbers of the  // form i+j+2ij from others where 1 <= i <= j  var marked = new Array(n / 2 + 500).fill(0);  // eliminate indexes which does not produce primes  for (let i = 1; i <= parseInt((nNew - 1) / 2); i++)  for (let j = (i * (i + 1)) << 1; j <= parseInt(n / 2); j = j + 2 * i + 1)  marked[j] = 1;  // Since 2 is a prime number  primes.push(2);  // Remaining primes are of the form 2*i + 1 such  // that marked[i] is false.  for (let i = 1; i <= parseInt(n / 2); i++)  if (marked[i] == 0)  primes.push(2 * i + 1);  }  // modified binary search to find nearest prime less than N  function binarySearch(left right n) {  if (left <= right) {  let mid = parseInt((left + right) / 2);  // base condition is if we are reaching at left  // corner or right corner of primes[] array then  // return that corner element because before or  // after that we don't have any prime number in  // primes array  if (mid == 0 || mid == primes.length - 1)  return primes[mid];  // now if n is itself a prime so it will be present  // in primes array and here we have to find nearest  // prime less than n so we will return primes[mid-1]  if (primes[mid] == n)  return primes[mid - 1];  // now if primes[mid]n that  // mean we reached at nearest prime  if (primes[mid] < n && primes[mid + 1] > n)  return primes[mid];  if (n < primes[mid])  return binarySearch(left mid - 1 n);  else  return binarySearch(mid + 1 right n);  }  return 0;  }  // Driver program to run the case  Sieve();  let n = 17;  document.write(binarySearch(0 primes.length - 1 n));  // This code is contributed by Potta Lokesh  </script> 

// CPP code to find the nearest prime to N // Using Trial Division method #include    #include  using namespace std; // Function to find the nearest prime to N // Using Trial Division method bool is_prime(int n) {  if (n <= 1) {  return false;  }  for (int i = 2; i <= sqrt(n); i++) {  if (n % i == 0) {  return false;  }  }  return true; } int nearest_prime(int n) {  int prime = 0;  for (int i = n-1; i >= 2; i--) {  if (is_prime(i)) {  prime = i;  break;  }  }  return prime; } int main() {  int n = 17;  int prime = nearest_prime(n);  if (prime == 0) {  cout << 'There is no prime less than ' << n << endl;  }  else {  cout << prime << endl;  }  return 0; } // This code is contributed by Susobhan Akhuli 

// Java code to find the nearest prime to N // Using Trial Division method import java.util.*; public class GFG {  // Function to find the nearest prime to N  // Using Trial Division method  public static boolean isPrime(int n)  {  if (n <= 1) {  return false;  }  for (int i = 2; i <= Math.sqrt(n); i++) {  if (n % i == 0) {  return false;  }  }  return true;  }  public static int nearestPrime(int n)  {  int prime = 0;  for (int i = n - 1; i >= 2; i--) {  if (isPrime(i)) {  prime = i;  break;  }  }  return prime;  }  public static void main(String[] args)  {  int n = 17;  int prime = nearestPrime(n);  if (prime == 0) {  System.out.println(  'There is no prime less than ' + n);  }  else {  System.out.println(prime);  }  } } // This code is contributed by Susobhan Akhuli 

# Python code to find the nearest prime to N # using Trial Division method import math # Function to check if a number is prime or not def is_prime(n): if n <= 1: return False for i in range(2 int(math.sqrt(n)) + 1): if n % i == 0: return False return True # Function to find the nearest prime to N # Using Trial Division method def nearest_prime(n): prime = 0 for i in range(n - 1 1 -1): if is_prime(i): prime = i break return prime # Main function to test the above functions if __name__ == '__main__': n = 17 prime = nearest_prime(n) if prime == 0: print(f'There is no prime less than {n}') else: print(prime) # This code is contributed by sankar. 

// C# code implementation for the above approach using System; public class GFG {  // Function to check if a number is prime  static bool IsPrime(int n)  {  if (n <= 1) {  return false;  }  for (int i = 2; i <= Math.Sqrt(n); i++) {  if (n % i == 0) {  return false;  }  }  return true;  }  // Function to find the nearest prime to n  static int NearestPrime(int n)  {  int prime = 0;  for (int i = n - 1; i >= 2; i--) {  if (IsPrime(i)) {  prime = i;  break;  }  }  return prime;  }  static public void Main()  {  // Code  int n = 17;  int prime = NearestPrime(n);  if (prime == 0) {  Console.WriteLine('There is no prime less than '  + n);  }  else {  Console.WriteLine(prime);  }  } } // This code is contributed by karthik. 

// Javascript code to find the nearest prime to N // Using Trial Division method // Function to check if a number is prime function isPrime(n) {  if (n <= 1) {  return false;  }  for (let i = 2; i <= Math.sqrt(n); i++) {  if (n % i === 0) {  return false;  }  }  return true; } // Function to find the nearest prime to n function nearestPrime(n) {  let prime = 0;  for (let i = n - 1; i >= 2; i--) {  if (isPrime(i)) {  prime = i;  break;  }  }  return prime; } let n = 17; let prime = nearestPrime(n); if (prime === 0) {  console.log('There is no prime less than ' + n); } else {  console.log(prime); } // This code is contributed by karthik.