Given an array Q[] consisting of N integers, the task for each element of the array Q[] is to check whether any of the numbers, formed by concatenating the first and the last digits of Q[i] is a prime number or not.
Examples:
Input: Q[] = {30, 66}
Output:
True
False
Explanation:
Q[0]: Possible combinations are 3 and 30. Since 3 is a prime number, the output is True.
Q[1]: Only possible combination is 66, which is not a prime number. Hence, the output is False.Input: Q[] = {2127, 13}
Output:
False
True
Explanation:
Q[0]: Possible combinations are 27 and 72. Since none of them is a prime number, the output is False.
Q[1]: Possible combinations are 13 and 31. Since both of them are prime numbers, the output is True.
Approach: The problem can be solved efficiently using the Sieve of Eratosthenes. Follow the steps below to solve the given problem:
- Since the highest number possible by combining a pair of digits is 99, pre-compute and store all prime numbers up to 99 using Sieve of Eratosthenes and store it in a boolean array, say prime[], where prime[i] = 0 (non-prime) and 1 (prime).
- Traverse the array Q[], and perform the following steps:
- Extract the last digit of Q[i] by performing Q[i] % 10 and store it in a variable, say last.
- Extract the first digit of Q[i] by continuously dividing Q[i] by 10 until Q[i] reduces to less than 10 and store it in a variable, say first.
- Now, generate the two possible combinations:
- first * 10 + last.
- last * 10 + first.
- For each of the above two combinations, check if any of them is a prime number or not.
- If any of the numbers formed are found to be prime then print True, otherwise False.
Below is the implementation of the above approach.
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Stores if i is prime (1)// or non-prime(0)int sieve[105];// Function to build sieve arrayvoid buildSieve(){ // Initialize all the values // in sieve equals to 1 for (int i = 2; i < 100; i++) sieve[i] = 1; // Sieve of Eratosthenes for (int i = 2; i < 100; i++) { // If current number is prime if (sieve[i] == 1) { // Set all multiples as non-prime for (int j = i * i; j < 100; j += i) sieve[j] = 0; } }}// Function to check if the numbers formed// by combining first and last digits// generates a prime number or notbool isAnyPrime(int first, int last){ int num1 = first * 10 + last; int num2 = last * 10 + first; // Check if any of the numbers // formed is a prime number or not if (sieve[num1] == 1 || sieve[num2] == 1) return true; else return false;}void performQueries(vector<int> q){ // Traverse the array of queries for (int i = 0; i < q.size(); i++) { int A = q[i]; // Extract the last digit int last = A % 10; // Extract the first digit int first; while (A >= 10) A = A / 10; first = A; // If any of the two // numbers is prime if (isAnyPrime(first, last)) cout << "True\n"; // Otherwise else cout << "False\n"; }}// Driver Codeint main(){ vector<int> q = { 30, 66 }; // Computes and stores // primes using Sieve buildSieve(); // Function call to perform queries performQueries(q); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG {// Stores if i is prime (1)// or non-prime(0)static int[] sieve = new int[105];// Function to build sieve arraystatic void buildSieve(){ // Initialize all the values // in sieve equals to 1 for (int i = 2; i < 100; i++) sieve[i] = 1; // Sieve of Eratosthenes for (int i = 2; i < 100; i++) { // If current number is prime if (sieve[i] == 1) { // Set all multiples as non-prime for (int j = i * i; j < 100; j += i) sieve[j] = 0; } }}// Function to check if the numbers formed// by combining first and last digits// generates a prime number or notstatic boolean isAnyPrime(int first, int last){ int num1 = first * 10 + last; int num2 = last * 10 + first; // Check if any of the numbers // formed is a prime number or not if (sieve[num1] == 1 || sieve[num2] == 1) return true; else return false;}static void performQueries(int[] q){ // Traverse the array of queries for (int i = 0; i < q.length; i++) { int A = q[i]; // Extract the last digit int last = A % 10; // Extract the first digit int first; while (A >= 10) A = A / 10; first = A; // If any of the two // numbers is prime if (isAnyPrime(first, last)) System.out.println("True\n"); // Otherwise else System.out.print("False\n"); }}// Driver Codepublic static void main(String[] args){ int[] q = { 30, 66 }; // Computes and stores // primes using Sieve buildSieve(); // Function call to perform queries performQueries(q);}}// This code is contributed by susmitakundugoaldanga. |
Python3
# Python 3 program for the above approach# Stores if i is prime (1)# or non-prime(0)sieve = [0 for i in range(105)]# Function to build sieve arraydef buildSieve(): global sieve # Initialize all the values # in sieve equals to 1 for i in range(2, 100): sieve[i] = 1 # Sieve of Eratosthenes for i in range(2, 100): # If current number is prime if (sieve[i] == 1): # Set all multiples as non-prime for j in range( i* i, 100, i): sieve[j] = 0# Function to check if the numbers formed# by combining first and last digits# generates a prime number or notdef isAnyPrime(first, last): global sieve num1 = first * 10 + last num2 = last * 10 + first # Check if any of the numbers # formed is a prime number or not if (sieve[num1] == 1 or sieve[num2] == 1): return True else: return Falsedef performQueries(q): # Traverse the array of queries for i in range(len(q)): A = q[i] # Extract the last digit last = A % 10 # Extract the first digit first = 0 while (A >= 10): A = A // 10 first = A # If any of the two # numbers is prime if (isAnyPrime(first, last)): print("True") # Otherwise else: print("False")# Driver Codeif __name__ == '__main__': q = [30, 66] # Computes and stores # primes using Sieve buildSieve() # Function call to perform queries performQueries(q) # This code is contributed by bgangwar59. |
C#
// C# program for above approach/*package whatever //do not write package name here */using System;public class GFG { // Stores if i is prime (1)// or non-prime(0)static int[] sieve = new int[105];// Function to build sieve arraystatic void buildSieve(){ // Initialize all the values // in sieve equals to 1 for (int i = 2; i < 100; i++) sieve[i] = 1; // Sieve of Eratosthenes for (int i = 2; i < 100; i++) { // If current number is prime if (sieve[i] == 1) { // Set all multiples as non-prime for (int j = i * i; j < 100; j += i) sieve[j] = 0; } }}// Function to check if the numbers formed// by combining first and last digits// generates a prime number or notstatic bool isAnyPrime(int first, int last){ int num1 = first * 10 + last; int num2 = last * 10 + first; // Check if any of the numbers // formed is a prime number or not if (sieve[num1] == 1 || sieve[num2] == 1) return true; else return false;}static void performQueries(int[] q){ // Traverse the array of queries for (int i = 0; i < q.Length; i++) { int A = q[i]; // Extract the last digit int last = A % 10; // Extract the first digit int first; while (A >= 10) A = A / 10; first = A; // If any of the two // numbers is prime if (isAnyPrime(first, last)) Console.Write("True\n"); // Otherwise else Console.Write("False\n"); }}// Driver codepublic static void Main(String[] args){ int[] q = { 30, 66 }; // Computes and stores // primes using Sieve buildSieve(); // Function call to perform queries performQueries(q);}}// This code is contributed by code_hunt. |
Javascript
<script>// javascript program for the above approach// Stores if i is prime (1)// or non-prime(0)var sieve = Array.from({length: 105}, (_, i) => 0);// Function to build sieve arrayfunction buildSieve(){ // Initialize all the values // in sieve equals to 1 for (i = 2; i < 100; i++) sieve[i] = 1; // Sieve of Eratosthenes for (i = 2; i < 100; i++) { // If current number is prime if (sieve[i] == 1) { // Set all multiples as non-prime for (j = i * i; j < 100; j += i) sieve[j] = 0; } }}// Function to check if the numbers formed// by combining first and last digits// generates a prime number or notfunction isAnyPrime(first , last){ var num1 = first * 10 + last; var num2 = last * 10 + first; // Check if any of the numbers // formed is a prime number or not if (sieve[num1] == 1 || sieve[num2] == 1) return true; else return false;}function performQueries(q){ // Traverse the array of queries for (i = 0; i < q.length; i++) { var A = q[i]; // Extract the last digit var last = A % 10; // Extract the first digit var first; while (A >= 10) A = A / 10; first = A; // If any of the two // numbers is prime if (isAnyPrime(first, last)) document.write("True<br>"); // Otherwise else document.write("False"); }}// Driver Codevar q = [ 30, 66 ];// Computes and stores// primes using SievebuildSieve();// Function call to perform queriesperformQueries(q);// This code is contributed by Princi Singh </script> |
Output:
True False
Time Complexity: O(N)
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!
