Given two integers L and R, denoting a range [L, R], the task is to find the smallest prime number present in the range.
Examples:
Input: L = 6, R = 11
Output: 7
Explanation: In the range of 6 to 11
6 is divisible by 1, 2, 3 and 6.
7 is divisible by 1 and 7, hence this is a prime and the first in the range.
So 7 is smallest prime in the given range.Input: L = 14, R = 19
Output: 17
Explanation: 14 is divisible by 1, 2, 7 and 14.
15 is divisible by 1, 3, 5 and 15.
16 is divisible by 1, 2, 4, 8 and 16.
17 is divisible by 1 and 17.
So, in the range of 14 to 19, 17 is the smallest prime.
Approach: The problem can be solved based on the following idea:
Traverse from L to R and check if the number is prime or not. The first prime number is the smallest, as we are traversing from smaller end to higher end.
Follow the steps mentioned below to implement the idea:
- Start iteration from i = L to R:
- Check if i is prime or not:
- For this run a loop from j = 2 to the square root of i:
- If i is divisible by any value of j, it is not a prime.
- Otherwise, if i is not divisible by any value of j, i is a prime.
- For this run a loop from j = 2 to the square root of i:
- If i is a prime, break the loop and i the smallest prime.
- Check if i is prime or not:
- Return the value of the smallest prime as the required answer.
Below is the implementation of the above approach:
C++
// C++ code to implement the idea:#include <bits/stdc++.h>using namespace std;// Function to check if the number// is a prime or notint isPrime(int n){ if (n < 2) { return 0; } else { for (int i = 2; i < sqrt(n); i++) { if (n % i == 0) return 0; } } return 1;}// Function to find the smallest// prime in rangeint minPrimeRange(int x, int y){ for (int i = x; i <= y; i++) { if (isPrime(i)) return i; } return -1;}// Driver codeint main(){ int L = 14, R = 19; // Function call int ans = minPrimeRange(L, R); cout << ans; return 0;} |
Java
import java.util.*;public class Main { // Function to check if the number is a prime or not public static boolean isPrime(int n) { if (n < 2) { return false; } else { for (int i = 2; i <= Math.sqrt(n); i++) { if (n % i == 0) return false; } } return true; } // Function to find the smallest prime in range public static int minPrimeRange(int x, int y) { for (int i = x; i <= y; i++) { if (isPrime(i)) return i; } return -1; } // Driver code public static void main(String[] args) { int L = 14, R = 19; // Function call int ans = minPrimeRange(L, R); System.out.println(ans); }} |
Python
import math# Function to check if the number is a prime or notdef isPrime(n): if n < 2: return False else: for i in range(2, int(math.sqrt(n))+1): if n % i == 0: return False return True# Function to find the smallest prime in rangedef minPrimeRange(x, y): for i in range(x, y+1): if isPrime(i): return i return -1# Driver codeif __name__ == "__main__": L = 14 R = 19 # Function call ans = minPrimeRange(L, R) print(ans) |
C#
using System;namespace PrimeRange{ class Program { // Function to check if the number // is a prime or not static bool IsPrime(int n) { if (n < 2) { return false; } else { for (int i = 2; i * i <= n; i++) { if (n % i == 0) return false; } } return true; } // Function to find the smallest // prime in range static int MinPrimeRange(int x, int y) { for (int i = x; i <= y; i++) { if (IsPrime(i)) return i; } return -1; } static void Main(string[] args) { int L = 14, R = 19; // Function call int ans = MinPrimeRange(L, R); Console.WriteLine(ans); } }}// This code is contributed by Dwaipayan Bandyopadhyay |
Javascript
// JS code to implement the approach:function isPrime(n) { if (n < 2) { return 0; } else { for (let i = 2; i <= Math.sqrt(n); i++) { if (n % i === 0) { return 0; } } } return 1;}function minPrimeRange(x, y) { for (let i = x; i <= y; i++) { if (isPrime(i)) { return i; } } return -1;}// Driver codeconst L = 14;const R = 19;// Function callconst ans = minPrimeRange(L, R);console.log(ans); |
17
Time Complexity: O(N√N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
