Dado un número N. La tarea es imprimir el primo más cercano si el número no es primo haciéndolo primo sumando números primos secuencialmente desde 2.
Ejemplos:
Entrada: N = 8
Salida: 13
8 no es primo, así que súmale el primer primo para obtener 10
10 no es primo, por lo tanto, suma el segundo primo, es decir, 3 para obtener 13 que es primo.
Entrada: N = 45
Salida: 47
Acercamiento Usando la criba de Eratóstenes , marque el índice primo por 1 en la lista isprime[] y almacene todos los números primos en una lista prime[] . Siga sumando números primos secuencialmente a N, hasta que se convierta en primo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to print the
// nearest prime number by
// sequentially adding the
// prime numbers
#include<bits/stdc++.h>
using namespace std;
// Function to store prime
// numbers using prime sieve
void prime_sieve(int MAX, vector<int> &isprime,
vector<int> &prime)
{
// iterate for all
// the numbers
int i = 2;
while (i * i <= MAX)
{
// If prime[p] is not changed,
// then it is a prime
if (isprime[i] == 1)
{
// append the prime
// to the list
prime.push_back(i);
// Update all multiples of p
for (int j = i * 2; j < MAX; j += i)
{
isprime[j] = 0;
}
}
i += 1;
}
}
// Function to print
// the nearest prime
int printNearest(int N)
{
int MAX = 1e6;
// store all the
// index with 1
vector<int> isprime(MAX, 1);
// 0 and 1 are not prime
isprime[0] = isprime[1] = 0;
// list to store
// prime numbers
vector<int> prime;
// variable to
// add primes
int i = 0;
// call the sieve function
prime_sieve(MAX, isprime, prime);
// Keep on adding prime
// numbers till the nearest
// prime number is achieved
while (!isprime[N])
{
N += prime[i];
i += 1;
}
// return the
// nearest prime
return N ;
}
// Driver Code
int main()
{
int N = 8;
printf("%d", printNearest(N));
return 0;
}
// This code is contributed
// by Harshit Saini
Java
// Java program to print the
// nearest prime number by
// sequentially adding the
// prime numbers
import java.util.*;
class GFG
{
// Function to store prime
// numbers using prime sieve
static void prime_sieve(int MAX, int []isprime,
Vector<Integer> prime)
{
// iterate for all
// the numbers
int i = 2;
while (i * i <= MAX)
{
// If prime[p] is not changed,
// then it is a prime
if (isprime[i] == 1)
{
// append the prime
// to the list
prime.add(i);
// Update all multiples of p
for (int j = i * 2;
j < MAX; j += i)
{
isprime[j] = 0;
}
}
i += 1;
}
}
// Function to print
// the nearest prime
static int printNearest(int N)
{
int MAX = (int) 1e6;
// store all the
// index with 1 except 0,1 index
int [] isprime = new int[MAX];
for(int i = 2; i < MAX; i++)
isprime[i] = 1;
// list to store
// prime numbers
Vector<Integer> prime = new Vector<Integer>();
// variable to add primes
int i = 0;
// call the sieve function
prime_sieve(MAX, isprime, prime);
// Keep on adding prime
// numbers till the nearest
// prime number is achieved
while (isprime[N] == 0)
{
N += prime.get(i);
i += 1;
}
// return the
// nearest prime
return N ;
}
// Driver Code
public static void main(String[] args)
{
int N = 8;
System.out.printf("%d", printNearest(N));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program to print the nearest prime # number by sequentially adding the prime numbers # Function to store prime numbers using prime sieve def prime_sieve(MAX, isprime, prime): # iterate for all the numbers i = 2 while (i * i <= MAX): # If prime[p] is not changed, # then it is a prime if (isprime[i] == 1): # append the prime to the list prime.append(i) # Update all multiples of p for j in range(i * 2, MAX, i): isprime[j] = 0 i += 1 # Function to print the nearest prime def printNearest(N): MAX = 10**6 # store all the index with 1 isprime = [1] * MAX # 0 and 1 are not prime isprime[0] = isprime[1] = 0 # list to store prime numbers prime = [] # variable to add primes i = 0 # call the sieve function prime_sieve(MAX, isprime, prime) # Keep on adding prime numbers # till the nearest prime number # is achieved while not isprime[N]: N += prime[i] i += 1 # return the nearest prime return N # Driver Code N = 8 print(printNearest(N))
C#
// C# program to print the
// nearest prime number by
// sequentially adding the
// prime numbers
using System;
using System.Collections.Generic;
class GFG
{
// Function to store prime
// numbers using prime sieve
static void prime_sieve(int MAX, int []isprime,
List<int> prime)
{
// iterate for all the numbers
int i = 2;
while (i * i <= MAX)
{
// If prime[p] is not changed,
// then it is a prime
if (isprime[i] == 1)
{
// append the prime to the list
prime.Add(i);
// Update all multiples of p
for (int j = i * 2;
j < MAX; j += i)
{
isprime[j] = 0;
}
}
i += 1;
}
}
// Function to print
// the nearest prime
static int printNearest(int N)
{
int MAX = (int) 1e6;
int i = 0;
// store all the
// index with 1 except 0,1 index
int [] isprime = new int[MAX];
for(i = 2; i < MAX; i++)
isprime[i] = 1;
// list to store
// prime numbers
List<int> prime = new List<int>();
// variable to add primes
i = 0;
// call the sieve function
prime_sieve(MAX, isprime, prime);
// Keep on adding prime
// numbers till the nearest
// prime number is achieved
while (isprime[N] == 0)
{
N += prime[i];
i += 1;
}
// return the
// nearest prime
return N;
}
// Driver Code
public static void Main(String[] args)
{
int N = 8;
Console.Write("{0}", printNearest(N));
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript program to print the
// nearest prime number by
// sequentially adding the
// prime numbers
// Function to store prime
// numbers using prime sieve
function prime_sieve(MAX, isprime, prime)
{
// iterate for all
// the numbers
var i = 2;
while (i * i <= MAX)
{
// If prime[p] is not changed,
// then it is a prime
if (isprime[i] == 1)
{
// append the prime
// to the list
prime.push(i);
// Update all multiples of p
for (var j = i * 2; j < MAX; j += i)
{
isprime[j] = 0;
}
}
i += 1;
}
}
// Function to print
// the nearest prime
function printNearest(N)
{
var MAX = 1e6;
// store all the
// index with 1
var isprime = Array(MAX).fill(1);
// 0 and 1 are not prime
isprime[0] = isprime[1] = 0;
// list to store
// prime numbers
var prime = [];
// variable to
// add primes
var i = 0;
// call the sieve function
prime_sieve(MAX, isprime, prime);
// Keep on adding prime
// numbers till the nearest
// prime number is achieved
while (!isprime[N])
{
N += prime[i];
i += 1;
}
// return the
// nearest prime
return N ;
}
// Driver Code
var N = 8;
document.write( printNearest(N));
// This code is contributed by rrrtnx.
</script>
Producción:
13
Complejidad de tiempo: O(N * log(logN))
Espacio auxiliar: O(N)