Dado un número entero N . La tarea es encontrar el N- ésimo número primo.
Ejemplos:
Entrada : 5
Salida : 11Entrada : 16
Salida : 53Entrada: 1049
Salida: 8377
Acercarse:
- Encuentra los números primos hasta MAX_SIZE usando Sieve of Eratosthenes .
- Almacene todos los números primos en un vector.
- Para un número N dado, devuelve el elemento en el índice (N-1) en un vector.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to the nth prime number
#include <bits/stdc++.h>
using namespace std;
// initializing the max value
#define MAX_SIZE 1000005
// Function to generate N prime numbers using
// Sieve of Eratosthenes
void SieveOfEratosthenes(vector<int>& primes)
{
// Create a boolean array "IsPrime[0..MAX_SIZE]" and
// initialize all entries it as true. A value in
// IsPrime[i] will finally be false if i is
// Not a IsPrime, else true.
bool IsPrime[MAX_SIZE];
memset(IsPrime, true, sizeof(IsPrime));
for (int p = 2; p * p < MAX_SIZE; p++) {
// If IsPrime[p] is not changed, then it is a prime
if (IsPrime[p] == true) {
// Update all multiples of p greater than or
// equal to the square of it
// numbers which are multiple of p and are
// less than p^2 are already been marked.
for (int i = p * p; i < MAX_SIZE; i += p)
IsPrime[i] = false;
}
}
// Store all prime numbers
for (int p = 2; p < MAX_SIZE; p++)
if (IsPrime[p])
primes.push_back(p);
}
// Driver Code
int main()
{
// To store all prime numbers
vector<int> primes;
// Function call
SieveOfEratosthenes(primes);
cout << "5th prime number is " << primes[4] << endl;
cout << "16th prime number is " << primes[15] << endl;
cout << "1049th prime number is " << primes[1048];
return 0;
}
Java
// Java program to the nth prime number
import java.util.ArrayList;
class GFG
{
// initializing the max value
static int MAX_SIZE = 1000005;
// To store all prime numbers
static ArrayList<Integer> primes =
new ArrayList<Integer>();
// Function to generate N prime numbers
// using Sieve of Eratosthenes
static void SieveOfEratosthenes()
{
// Create a boolean array "IsPrime[0..MAX_SIZE]"
// and initialize all entries it as true.
// A value in IsPrime[i] will finally be false
// if i is Not a IsPrime, else true.
boolean [] IsPrime = new boolean[MAX_SIZE];
for(int i = 0; i < MAX_SIZE; i++)
IsPrime[i] = true;
for (int p = 2; p * p < MAX_SIZE; p++)
{
// If IsPrime[p] is not changed,
// then it is a prime
if (IsPrime[p] == true)
{
// Update all multiples of p greater than or
// equal to the square of it
// numbers which are multiple of p and are
// less than p^2 are already been marked.
for (int i = p * p; i < MAX_SIZE; i += p)
IsPrime[i] = false;
}
}
// Store all prime numbers
for (int p = 2; p < MAX_SIZE; p++)
if (IsPrime[p] == true)
primes.add(p);
}
// Driver Code
public static void main (String[] args)
{
// Function call
SieveOfEratosthenes();
System.out.println("5th prime number is " +
primes.get(4));
System.out.println("16th prime number is " +
primes.get(15));
System.out.println("1049th prime number is " +
primes.get(1048));
}
}
// This code is contributed by ihritik
Python3
# Python3 program to the nth prime number
primes = []
# Function to generate N prime numbers using
# Sieve of Eratosthenes
def SieveOfEratosthenes():
n = 1000005
# Create a boolean array "prime[0..n]" and
# initialize all entries it as true. A value
# in prime[i] will finally be false if i is
# Not a prime, else true.
prime = [True for i in range(n + 1)]
p = 2
while (p * p <= n):
# If prime[p] is not changed,
# then it is a prime
if (prime[p] == True):
# Update all multiples of p
for i in range(p * p, n + 1, p):
prime[i] = False
p += 1
# Print all prime numbers
for p in range(2, n + 1):
if prime[p]:
primes.append(p)
# Driver code
if __name__=='__main__':
# Function call
SieveOfEratosthenes()
print("5th prime number is", primes[4]);
print("16th prime number is", primes[15]);
print("1049th prime number is", primes[1048]);
# This code is contributed by grand_master
C#
// C# program to the nth prime number
using System;
using System.Collections;
class GFG
{
// initializing the max value
static int MAX_SIZE = 1000005;
// To store all prime numbers
static ArrayList primes = new ArrayList();
// Function to generate N prime numbers using
// Sieve of Eratosthenes
static void SieveOfEratosthenes()
{
// Create a boolean array "IsPrime[0..MAX_SIZE]"
// and initialize all entries it as true.
// A value in IsPrime[i] will finally be false
// if i is Not a IsPrime, else true.
bool [] IsPrime = new bool[MAX_SIZE];
for(int i = 0; i < MAX_SIZE; i++)
IsPrime[i] = true;
for (int p = 2; p * p < MAX_SIZE; p++)
{
// If IsPrime[p] is not changed,
// then it is a prime
if (IsPrime[p] == true)
{
// Update all multiples of p greater than or
// equal to the square of it
// numbers which are multiple of p and are
// less than p^2 are already been marked.
for (int i = p * p; i < MAX_SIZE; i += p)
IsPrime[i] = false;
}
}
// Store all prime numbers
for (int p = 2; p < MAX_SIZE; p++)
if (IsPrime[p] == true)
primes.Add(p);
}
// Driver Code
public static void Main ()
{
// Function call
SieveOfEratosthenes();
Console.WriteLine("5th prime number is " +
primes[4]);
Console.WriteLine("16th prime number is " +
primes[15]);
Console.WriteLine("1049th prime number is " +
primes[1048]);
}
}
// This code is contributed by ihritik
Javascript
<script>
// Javascript program to the nth prime number
// initializing the max value
var MAX_SIZE = 1000005;
// Function to generate N prime numbers using
// Sieve of Eratosthenes
function SieveOfEratosthenes(primes)
{
// Create a boolean array
// "IsPrime[0..MAX_SIZE]" and
// initialize all entries it as true.
// A value in
// IsPrime[i] will finally be false if i is
// Not a IsPrime, else true.
var IsPrime = Array(MAX_SIZE).fill(true);
var p,i;
for (p = 2; p * p < MAX_SIZE;p++)
{
// If IsPrime[p] is not changed,
// then it is a prime
if (IsPrime[p] == true)
{
// Update all multiples of p
// greater than or
// equal to the square of it
// numbers which are multiple
// of p and are
// less than p^2 are already
// been marked.
for(i = p * p; i < MAX_SIZE; i += p)
IsPrime[i] = false;
}
}
// Store all prime numbers
for (p = 2; p < MAX_SIZE; p++)
if (IsPrime[p])
primes.push(p);
}
// Driver Code
// To store all prime numbers
var primes = [];
// Function call
SieveOfEratosthenes(primes);
document.write(
"5th prime number is "+primes[4]+"<br>"
);
document.write(
"16th prime number is "+primes[15]+"<br>"
);
document.write(
"1049th prime number is "+primes[1048]+"<br>"
);
</script>
Producción
5th prime number is 11 16th prime number is 53 1049th prime number is 8377
Otro enfoque :
- para encontrar un número primo en una posición dada, escriba una función isPrime para verificar que el número sea primo o no
- escribir una función para obtener un número primo en la posición dada
A continuación se muestra la implementación del enfoque anterior:
C++
// c++ program to find the n-th prime number
#include <bits/stdc++.h>
using namespace std;
// function to check given number is prime or not
// basic idea is numbers not divided by any primes are primes
int isPrime(int k)
{
// Corner cases
if (k <= 1)
return 0;
if (k==2 || k==3)
return 1;
// below 5 there is only two prime numbers 2 and 3
if (k % 2 == 0 || k % 3 == 0)
return 0;
// Using concept of prime number can be represented in form of (6*k + 1) or(6*k - 1)
for (int i = 5; i * i <= k; i = i + 6)
if (k % i == 0 || k % (i + 2) == 0)
return 0;
return 1;
}
// function which gives prime at position n
int nThPrime(int n)
{
int i=2;
while(n>0)
{
// each time if a prime number found decrease n
if(isPrime(i))
n--;
i++; //increase the integer to go ahead
}
i-=1; // since decrement of k is being done before
//Increment of i , so i should be decreased by 1
return i;
}
int main()
{
cout<<"5th prime number is : "<<nThPrime(5)<<"\n";
cout<<"7th prime number is : "<<nThPrime(7)<<"\n";
cout<<"10th prime number is : "<<nThPrime(10)<<"\n";
return 0;
}
// This code is contributed by Ujjwal Kumar Bhardwaj
Producción
5th prime number is : 11 7th prime number is : 17 10th prime number is : 29