Dada una array Q[] que consta de N enteros, la tarea de cada elemento de la array Q[] es verificar si alguno de los números, formados al concatenar el primero y el último dígito de Q[i], es un número primo o no.
Ejemplos:
Entrada: Q[] = {30, 66}
Salida:
Verdadero
Falso
Explicación:
Q[0]: Las combinaciones posibles son 3 y 30. Dado que 3 es un número primo, la salida es Verdadero.
P[1]: La única combinación posible es 66, que no es un número primo. Por lo tanto, la salida es Falsa.Entrada: Q[] = {2127, 13}
Salida:
Falso
Verdadero
Explicación:
P[0]: Las combinaciones posibles son 27 y 72. Como ninguna de ellas es un número primo, la salida es Falso.
P[1]: Las combinaciones posibles son 13 y 31. Dado que ambos son números primos, el resultado es Verdadero.
Enfoque: El problema se puede resolver eficientemente usando el
- hasta 99 usando Tamiz de Eratóstenes y guárdelo en una array booleana, digamos prime[] , donde prime[i] = 0 (no primo) y 1 (principal).
-
-
- último * 10 + primero .
- Para cada una de las dos combinaciones anteriores, comprueba si alguna de ellas es un número primo o no .
- Si se encuentra que alguno de los números formados es primo, imprima Verdadero, de lo contrario Falso.
-
A continuación se muestra la implementación del enfoque anterior.
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 array
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 not
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;
}
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 Code
int 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 approach
import 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 array
static 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 not
static 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 Code
public 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 array
def 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 not
def 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 False
def 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 Code
if __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 array
static 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 not
static 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 code
public 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 array
function 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 not
function 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 Code
var q = [ 30, 66 ];
// Computes and stores
// primes using Sieve
buildSieve();
// Function call to perform queries
performQueries(q);
// This code is contributed by Princi Singh
</script>
Producción:
True False
Complejidad temporal: O(N) Espacio
auxiliar : O(1)
Publicación traducida automáticamente
Artículo escrito por patelajeet y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA