Dada una array de enteros A[] de tamaño N , la tarea es encontrar los números primos justo menores y mayores que A[i] (para todo 0<=i<N ).
Ejemplos:
Entrada: A={17, 28}, N=2
Salida:
13 19
23 29
Explicación:
13 es el número primo justo menor que 17.
19 es el número primo justo mayor que 17.
23 es el número primo justo menor que 28
29 es el número primo justo mayor que 28 .Entrada: A={126, 64, 2896, 156}, N=4
Salida:
113 127
61 67
2887 2897
151 157
Enfoque ingenuo:
Observación: la brecha primaria máxima para números menores de 10 9 es 292.
El enfoque ingenuo sería verificar la primalidad verificando si un número tiene algún factor que no sea 1 y sí mismo. Siga los pasos a continuación para resolver el problema:
Atraviese la array A y, para cada índice actual i , haga lo siguiente:
- Iterar desde A[i]-1 en orden descendente, y para cada índice j actual , hacer lo siguiente:
- Compruebe si j es primo o no comprobando si tiene algún factor que no sea 1 y él mismo.
- Si j es primo, imprima j y termine el ciclo interno. Esto le da al número primo un poco menos que A[i] .
- Iterar desde A[i]+1 en orden ascendente, y para cada índice j actual , hacer lo siguiente:
- Compruebe si j es primo o no comprobando si tiene algún factor que no sea 1 y él mismo.
- Si j es primo, imprima j y termine el ciclo interno. Esto le da al número primo un poco menos que A[i],
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;
// Utility function to check
// for primality of a number X by
// checking whether X haACCs any
// factors other than 1 and itself.
bool isPrime(int X)
{
for (int i = 2; i * i <= X; i++)
if (X % i == 0) // Factor found
return false;
return true;
}
// Function to print primes
// just less than and just greater
// than of each element in an array
void printPrimes(int A[], int N)
{
// Traverse the array
for (int i = 0; i < N; i++) {
// Traverse for finding prime
// just less than A[i]
for (int j = A[i] - 1;; j--) {
// Prime just less than A[i] found
if (isPrime(j)) {
cout << j << " ";
break;
}
}
// Traverse for finding prime
// just greater than A[i]
for (int j = A[i] + 1;; j++) {
// Prime just greater than A[i] found
if (isPrime(j)) {
cout << j << " ";
break;
}
}
cout << endl;
}
}
// Driver code
int main()
{
// Input
int A[] = { 17, 28 };
int N = sizeof(A) / sizeof(A[0]);
// Function call
printPrimes(A, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG{
// Utility function to check
// for primality of a number X by
// checking whether X has any
// factors other than 1 and itself.
static boolean isPrime(int X)
{
for(int i = 2; i * i <= X; i++)
// Factor found
if (X % i == 0)
return false;
return true;
}
// Function to print primes
// just less than and just greater
// than of each element in an array
static void printPrimes(int A[], int N)
{
// Traverse the array
for(int i = 0; i < N; i++)
{
// Traverse for finding prime
// just less than A[i]
for(int j = A[i] - 1;; j--)
{
// Prime just less than A[i] found
if (isPrime(j))
{
System.out.print(j + " ");
break;
}
}
// Traverse for finding prime
// just greater than A[i]
for(int j = A[i] + 1;; j++)
{
// Prime just greater than A[i] found
if (isPrime(j))
{
System.out.print( j + " ");
break;
}
}
System.out.println();
}
}
// Driver code
public static void main(String[] args)
{
// Input
int A[] = { 17, 28 };
int N = A.length;
// Function call
printPrimes(A, N);
}
}
// This code is contributed by sanjoy_62
Python3
# Python3 program for the above approach
from math import sqrt
# Utility function to check
# for primality of a number X by
# checking whether X haACCs any
# factors other than 1 and itself.
def isPrime(X):
for i in range(2, int(sqrt(X)) + 1, 1):
if (X % i == 0):
# Factor found
return False
return True
# Function to print primes
# just less than and just greater
# than of each element in an array
def printPrimes(A, N):
# Traverse the array
for i in range(N):
# Traverse for finding prime
# just less than A[i]
j = A[i] - 1
while(1):
# Prime just less than A[i] found
if (isPrime(j)):
print(j, end = " ")
break
j -= 1
# Traverse for finding prime
# just greater than A[i]
j = A[i] + 1
while (1):
# Prime just greater than A[i] found
if (isPrime(j)):
print(j, end = " ")
break
j += 1
print("\n", end = "")
# Driver code
if __name__ == '__main__':
# Input
A = [ 17, 28 ]
N = len(A)
# Function call
printPrimes(A, N)
# This code is contributed by SURENDRA_GANGWAR
C#
// C# program for the above approach
using System;
class GFG{
// Utility function to check
// for primality of a number X by
// checking whether X has any
// factors other than 1 and itself.
static bool isPrime(int X)
{
for(int i = 2; i * i <= X; i++)
// Factor found
if (X % i == 0)
return false;
return true;
}
// Function to print primes
// just less than and just greater
// than of each element in an array
static void printPrimes(int[] A, int N)
{
// Traverse the array
for(int i = 0; i < N; i++)
{
// Traverse for finding prime
// just less than A[i]
for(int j = A[i] - 1;; j--)
{
// Prime just less than A[i] found
if (isPrime(j))
{
Console.Write(j + " ");
break;
}
}
// Traverse for finding prime
// just greater than A[i]
for(int j = A[i] + 1;; j++)
{
// Prime just greater than A[i] found
if (isPrime(j))
{
Console.Write(j + " ");
break;
}
}
Console.WriteLine();
}
}
// Driver code
public static void Main()
{
// Input
int []A = { 17, 28 };
int N = A.Length;
// Function call
printPrimes(A, N);
}
}
// This code is contributed by subhammahato348
Javascript
<script>
// Javascript program for the above approach
// Utility function to check
// for primality of a number X by
// checking whether X haACCs any
// factors other than 1 and itself.
function isPrime(X) {
for (let i = 2; i * i <= X; i++)
if (X % i == 0) // Factor found
return false;
return true;
}
// Function to print primes
// just less than and just greater
// than of each element in an array
function printPrimes(A, N)
{
// Traverse the array
for (let i = 0; i < N; i++)
{
// Traverse for finding prime
// just less than A[i]
for (let j = A[i] - 1; ; j--)
{
// Prime just less than A[i] found
if (isPrime(j)) {
document.write(j + " ");
break;
}
}
// Traverse for finding prime
// just greater than A[i]
for (let j = A[i] + 1; ; j++)
{
// Prime just greater than A[i] found
if (isPrime(j)) {
document.write(j + " ");
break;
}
}
document.write("<br>");
}
}
// Driver code
// Input
let A = [17, 28];
let N = A.length;
// Function call
printPrimes(A, N);
// This code is contributed by _saurabh_jaiswal.
</script>
Producción
13 19 23 29
Complejidad de tiempo: O(N*G*√M), donde G es la brecha primaria máxima y M es el elemento más grande en A.
Espacio auxiliar: O(1)
Enfoque eficiente 1: en lugar de buscar números individuales, todos los números primos se pueden volver a calcular con la criba de Eratóstenes.
A continuación se muestra la implementación del enfoque anterior:
C++
#include <bits/stdc++.h>
using namespace std;
const int M = 1e6;
// Boolean array to store
// if a number is prime or not
bool isPrime[M];
void SieveOfEratosthenes()
{
// assigh value false
// to the boolean array isprime
memset(isPrime, true, sizeof(isPrime));
for (int i = 2; i * i <= M; i++) {
// If isPrime[i] is not changed,
// then it is a prime
if (isPrime[i]) {
// Update all multiples of i greater than or
// equal to the square of it numbers which are
// multiple of i and are less than i^2 are
// already been marked.
for (int j = i * i; j < M; j += i)
isPrime[j] = false;
}
}
}
// Function to print primes
// just less than and just greater
// than of each element in an array
void printPrimes(int A[], int N)
{
// Precalculating
SieveOfEratosthenes();
// Traverse the array
for (int i = 0; i < N; i++) {
// Traverse for finding
// prime just less than A[i]
for (int j = A[i] - 1;; j--) {
// Prime just less than A[i] found
if (isPrime[j]) {
cout << j << " ";
break;
}
}
// Traverse for finding
// prime just greater than A[i]
for (int j = A[i] + 1;; j++) {
// Prime just greater than A[i] found
if (isPrime[j]) {
cout << j << " ";
break;
}
}
cout << endl;
}
}
// Driver code
int main()
{
// Input
int A[] = { 17, 28 };
int N = sizeof(A) / sizeof(A[0]);
// Function call
printPrimes(A, N);
return 0;
}
Java
import java.util.*;
class GFG{
static int M = 1000000;
// Boolean array to store
// if a number is prime or not
static boolean isPrime[] = new boolean[M];
static void SieveOfEratosthenes()
{
// Assigh value false
// to the boolean array isprime
Arrays.fill(isPrime, true);
for(int i = 2; i * i <= M; i++)
{
// If isPrime[i] is not changed,
// then it is a prime
if (isPrime[i])
{
// Update all multiples of i greater than or
// equal to the square of it numbers which are
// multiple of i and are less than i^2 are
// already been marked.
for(int j = i * i; j < M; j += i)
isPrime[j] = false;
}
}
}
// Function to print primes
// just less than and just greater
// than of each element in an array
static void printPrimes(int A[], int N)
{
// Precalculating
SieveOfEratosthenes();
// Traverse the array
for(int i = 0; i < N; i++)
{
// Traverse for finding
// prime just less than A[i]
for(int j = A[i] - 1;; j--)
{
// Prime just less than A[i] found
if (isPrime[j])
{
System.out.print( j + " ");
break;
}
}
// Traverse for finding
// prime just greater than A[i]
for(int j = A[i] + 1;; j++)
{
// Prime just greater than A[i] found
if (isPrime[j])
{
System.out.print(j + " ");
break;
}
}
System.out.println();
}
}
// Driver code
public static void main(String[] args)
{
// Input
int A[] = { 17, 28 };
int N = A.length;
// Function call
printPrimes(A, N);
}
}
// This code is contributed by sanjoy_62
C#
using System;
class GFG {
static int M = 1000000;
// Boolean array to store
// if a number is prime or not
static bool[] isPrime = new bool[M];
static void SieveOfEratosthenes()
{
// Assigh value false
// to the boolean array isprime
Array.Fill(isPrime, true);
for (int i = 2; i * i <= M; i++) {
// If isPrime[i] is not changed,
// then it is a prime
if (isPrime[i]) {
// Update all multiples of i greater than or
// equal to the square of it numbers which
// are multiple of i and are less than i^2
// are already been marked.
for (int j = i * i; j < M; j += i)
isPrime[j] = false;
}
}
}
// Function to print primes
// just less than and just greater
// than of each element in an array
static void printPrimes(int[] A, int N)
{
// Precalculating
SieveOfEratosthenes();
// Traverse the array
for (int i = 0; i < N; i++) {
// Traverse for finding
// prime just less than A[i]
for (int j = A[i] - 1;; j--) {
// Prime just less than A[i] found
if (isPrime[j]) {
Console.Write(j + " ");
break;
}
}
// Traverse for finding
// prime just greater than A[i]
for (int j = A[i] + 1;; j++) {
// Prime just greater than A[i] found
if (isPrime[j]) {
Console.Write(j + " ");
break;
}
}
Console.WriteLine();
}
}
// Driver code
public static void Main()
{
// Input
int[] A = { 17, 28 };
int N = A.Length;
// Function call
printPrimes(A, N);
}
}
// This code is contributed by subham348.
Javascript
<script>
const M = 1000000;
// Boolean array to store
// if a number is prime or not
let isPrime = new Array(M).fill(true);
function SieveOfEratosthenes()
{
for (let i = 2; i * i <= M; i++) {
// If isPrime[i] is not changed,
// then it is a prime
if (isPrime[i]) {
// Update all multiples of i greater than or
// equal to the square of it numbers which are
// multiple of i and are less than i^2 are
// already been marked.
for (let j = i * i; j < M; j += i)
isPrime[j] = false;
}
}
}
// Function to print primes
// just less than and just greater
// than of each element in an array
function printPrimes(A, N)
{
// Precalculating
SieveOfEratosthenes();
// Traverse the array
for (let i = 0; i < N; i++) {
// Traverse for finding
// prime just less than A[i]
for (let j = A[i] - 1;; j--) {
// Prime just less than A[i] found
if (isPrime[j]) {
document.write(j + " ");
break;
}
}
// Traverse for finding
// prime just greater than A[i]
for (let j = A[i] + 1;; j++) {
// Prime just greater than A[i] found
if (isPrime[j]) {
document.write(j + " ");
break;
}
}
document.write("<br>");
}
}
// Driver code
// Input
let A = [ 17, 28 ];
let N = A.length;
// Function call
printPrimes(A, N);
</script>
Producción
13 19 23 29
Complejidad de tiempo: O(N*G+MLog(Log(M))), donde G es la brecha primaria máxima y M es el elemento más grande en A.
Espacio auxiliar: O(M)
Enfoque eficiente 2: se puede utilizar la prueba de primalidad de Millar-Rabin .
C++
#include <bits/stdc++.h>
using namespace std;
// Utility function to do modular exponentiation.
// It returns (x^y) % p
int power(int x, unsigned int y, int p)
{
int res = 1; // Initialize result
x = x % p; // Update x if it is more than or
// equal to p
while (y > 0) {
// If y is odd, multiply x with result
if (y & 1)
res = (res * x) % p;
// y must be even now
y = y >> 1; // y = y/2
x = (x * x) % p;
}
return res;
}
// This function is called for all k trials.
// It returns false if n is composite
// and returns true if n is probably prime.
// d is an odd number such that
// d*2<sup>r</sup> = n-1 for some r >= 1
bool miillerTest(int d, int n)
{
// Pick a random number in [2..n-2]
// Corner cases make sure that n > 4
int a = 2 + rand() % (n - 4);
// Compute a^d % n
int x = power(a, d, n);
if (x == 1 || x == n - 1)
return true;
// Keep squaring x while one
// of the following doesn't happen
// (i) d does not reach n-1
// (ii) (x^2) % n is not 1
// (iii) (x^2) % n is not n-1
while (d != n - 1) {
x = (x * x) % n;
d *= 2;
if (x == 1)
return false;
if (x == n - 1)
return true;
}
// Return composite
return false;
}
// It returns false if n is
// composite and returns true if n
// is probably prime.
// k determines accuracy level. Higher
// value of k indicates more accuracy.
bool isPrime(int n)
{
// number of iterations
int k = 4;
// Corner cases
if (n <= 1 || n == 4)
return false;
if (n <= 3)
return true;
// Find r such that
// n = 2^d * r + 1 for some r >= 1
int d = n - 1;
while (d % 2 == 0)
d /= 2;
// Iterate given number of 'k' times
for (int i = 0; i < k; i++)
if (!miillerTest(d, n))
return false;
return true;
}
// Function to print primes
// just less than and just greater
// than of each element in an array
void printPrimes(int A[], int N)
{
// Precalculating
// Traverse the array
for (int i = 0; i < N; i++) {
// Traverse for finding
// prime just less than A[i]
for (int j = A[i] - 1;; j--) {
// Prime just less than A[i] found
if (isPrime(j)) {
cout << j << " ";
break;
}
}
// Traverse for finding
// prime just greater than A[i]
for (int j = A[i] + 1;; j++) {
// Prime just greater than A[i] found
if (isPrime(j)) {
cout << j << " ";
break;
}
}
cout << endl;
}
}
// Driver code
int main()
{
// Input
int A[] = { 17, 28 };
int N = sizeof(A) / sizeof(A[0]);
// Function call
printPrimes(A, N);
return 0;
}
Java
import java.util.*;
class GFG
{
// Utility function to do modular exponentiation.
// It returns (x^y) % p
static int power(int x, int y, int p)
{
int res = 1; // Initialize result
x = x % p; // Update x if it is more than or
// equal to p
while (y > 0)
{
// If y is odd, multiply x with result
if (y %2==1)
res = (res * x) % p;
// y must be even now
y = y >> 1; // y = y/2
x = (x * x) % p;
}
return res;
}
// This function is called for all k trials.
// It returns false if n is composite
// and returns true if n is probably prime.
// d is an odd number such that
// d*2<sup>r</sup> = n-1 for some r >= 1
static boolean miillerTest(int d, int n)
{
// Pick a random number in [2..n-2]
// Corner cases make sure that n > 4
int a = 2 + (int)(Math.random()*100000) % (n - 4);
// Compute a^d % n
int x = power(a, d, n);
if (x == 1 || x == n - 1)
return true;
// Keep squaring x while one
// of the following doesn't happen
// (i) d does not reach n-1
// (ii) (x^2) % n is not 1
// (iii) (x^2) % n is not n-1
while (d != n - 1) {
x = (x * x) % n;
d *= 2;
if (x == 1)
return false;
if (x == n - 1)
return true;
}
// Return composite
return false;
}
// It returns false if n is
// composite and returns true if n
// is probably prime.
// k determines accuracy level. Higher
// value of k indicates more accuracy.
static boolean isPrime(int n)
{
// number of iterations
int k = 4;
// Corner cases
if (n <= 1 || n == 4)
return false;
if (n <= 3)
return true;
// Find r such that
// n = 2^d * r + 1 for some r >= 1
int d = n - 1;
while (d % 2 == 0)
d /= 2;
// Iterate given number of 'k' times
for (int i = 0; i < k; i++)
if (!miillerTest(d, n))
return false;
return true;
}
// Function to print primes
// just less than and just greater
// than of each element in an array
static void printPrimes(int A[], int N)
{
// Precalculating
// Traverse the array
for (int i = 0; i < N; i++)
{
// Traverse for finding
// prime just less than A[i]
for (int j = A[i] - 1;; j--)
{
// Prime just less than A[i] found
if (isPrime(j)) {
System.out.print(j+ " ");
break;
}
}
// Traverse for finding
// prime just greater than A[i]
for (int j = A[i] + 1;; j++)
{
// Prime just greater than A[i] found
if (isPrime(j)) {
System.out.print(j+ " ");
break;
}
}
System.out.println();
}
}
// Driver code
public static void main(String[] args)
{
// Input
int A[] = { 17, 28 };
int N = A.length;
// Function call
printPrimes(A, N);
}
}
// This code is contributed by gauravrajput1
Producción
13 19 23 29
Complejidad de tiempo: O(N*G*KLog 3 M), donde G es la brecha primaria máxima y M es el elemento más grande en A. Aquí, K=4
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por satyamkant2805 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA