Check if number can be made prime by deleting a single digit
Given an integer N, the task is to check if it is possible to make N prime by deleting any single digit from N.
Examples:
Input: N = 610
Output: Yes
Explanation:
Deleting 0 from 610, we get 61 which is prime.Input: N = 68
Output: No
Approach: The idea is to convert N to a string. Now iterate for every digit of string and Delete character at index i from string and then convert the string after deleting character at index i to an integer, Now check if this integer is a prime, then return true. Otherwise, finally return false.
Below is the implementation of the above approach:
C++
// C++ implementation to check if a number// becomes prime by deleting any digit#include <bits/stdc++.h> using namespace std; // Function to check if N is prime bool isPrime(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 (int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false; return true; } // Function to delete character at index i// from given string str string deleteIth(string str, int i) { // Deletes character at position 4 str.erase(str.begin() + i); return str; } // Function to check if a number// becomes prime by deleting any digitbool isPrimePossible(int N) { // Converting the number to string string s = to_string(N); // length of string int l = s.length(); // number should not be // of single digit if (l < 2) return false; // Loop to find all numbers // after deleting a single digit for (int i = 0; i < l ; i++) { // Deleting ith character // from the string string str = deleteIth(s, i); // converting string to int int num = stoi(str); if (isPrime(num)) return true; } return false; } // Driver Code int main() { int N = 610; isPrimePossible(N) ? cout << "Yes" : cout << "No"; return 0;} |
Java
// Java implementation to check if a number// becomes prime by deleting any digitimport java.util.*;class GFG{ // Function to check if N is prime static boolean isPrime(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 (int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false; return true; } // Function to delete character at index i // from given String str static String deleteIth(String str, int i) { // Deletes character at position 4 str = str.substring(0, i) + str.substring(i + 1); return str; } // Function to check if a number // becomes prime by deleting any digit static boolean isPrimePossible(int N) { // Converting the number to String String s = String.valueOf(N); // length of String int l = s.length(); // number should not be // of single digit if (l < 2) return false; // Loop to find all numbers // after deleting a single digit for (int i = 0; i < l; i++) { // Deleting ith character // from the String String str = deleteIth(s, i); // converting String to int int num = Integer.valueOf(str); if (isPrime(num)) return true; } return false; } // Driver Code public static void main(String[] args) { int N = 610; if (isPrimePossible(N)) System.out.print("Yes"); else System.out.print("No"); }}// This code is contributed by Rajput-Ji |
Python3
# Python3 implementation to check if a number# becomes prime by deleting any digit# Function to check if N is prime#from builtins import rangedef 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; for i in range(5, int(n**1/2), 6): if (n % i == 0 or n % (i + 2) == 0): return False; return True;# Function to delete character at index i# from given String strdef deleteIth(str, i): # Deletes character at position 4 str = str[0:i] + str[i + 1:]; return str;# Function to check if a number# becomes prime by deleting any digitdef isPrimePossible(N): # Converting the number to String s = str(N); # length of String l = len(s); # number should not be # of single digit if (l < 2): return False; # Loop to find all numbers # after deleting a single digit for i in range(l): # Deleting ith character # from the String str1 = deleteIth(s, i); # converting String to int num = int(str1); if (isPrime(num)): return True; return False;# Driver Codeif __name__ == '__main__': N = 610; if (isPrimePossible(N)): print("Yes"); else: print("No");# This code is contributed by Rajput-Ji |
C#
// C# implementation to check if a number// becomes prime by deleting any digitusing System;class GFG{// Function to check if N is primestatic bool isPrime(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(int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false; return true;}// Function to delete character at index i// from given String strstatic String deleteIth(String str, int i){ // Deletes character at position 4 str = str.Substring(0, i) + str.Substring(i + 1); return str;}// Function to check if a number// becomes prime by deleting any digitstatic bool isPrimePossible(int N){ // Converting the number to String String s = String.Join("", N); // length of String int l = s.Length; // number should not be // of single digit if (l < 2) return false; // Loop to find all numbers // after deleting a single digit for(int i = 0; i < l; i++) { // Deleting ith character // from the String String str = deleteIth(s, i); // converting String to int int num = Int32.Parse(str); if (isPrime(num)) return true; } return false;}// Driver Codepublic static void Main(String[] args){ int N = 610; if (isPrimePossible(N)) Console.Write("Yes"); else Console.Write("No");}}// This code is contributed by Rajput-Ji |
Javascript
<script>// JavaScript implementation to check if a number// becomes prime by deleting any digit// Function to check if N is prime function 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 delete character at index i // from given String str function deleteIth(str, i) { // Deletes character at position 4 str = str.substr(0, i) + str.substr(i + 1); return str; } // Function to check if a number // becomes prime by deleting any digit function isPrimePossible(N) { // Converting the number to String let s = N.toString(); // length of String let l = s.length; // number should not be // of single digit if (l < 2) return false; // Loop to find all numbers // after deleting a single digit for (let i = 0; i < l; i++) { // Deleting ith character // from the String let str = deleteIth(s, i); // converting String to let let num = parseInt(str); if (isPrime(num)) return true; } return false; }// Driver Code let N = 610; if (isPrimePossible(N)) document.write("Yes"); else document.write("No"); </script> |
Output
Yes
Time Complexity: O(D)
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 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
