java - usando - Cálculo e impresión del enésimo número primo

numeros primos en java con while

Question

Estoy tratando de calcular los números primos, que ya he hecho. Pero quiero calcular e imprimir SÓLO el enésimo número primo (entrada del usuario), mientras calculo el resto (no se imprimirán), solo se imprimirá el enésimo número primo.

Esto es lo que he escrito hasta ahora:

import java.util.Scanner;
/**
 * Calculates the nth prime number
 * @author {Zyst}
 */
public class Prime {
    public static void main(String[] args) {

        Scanner input = new Scanner(System.in);
        int n, 
            i = 2, 
            x = 2;

        System.out.printf("This program calculates the nth Prime number/n");
        System.out.printf("Please enter the nth prime number you want to find: ");
        n = input.nextInt();

        for(i = 2, x = 2; i <= n; i++) {
            for(x = 2; x < i; x++) {
                if(i % x == 0) {
                    break;
                }
            }
            if(x == i) {
                System.out.printf("/n%d is prime", x);
            }
        }
    }
}

Este es el programa que escribí para calcular los números primos de 1 a n. Sin embargo, quiero que solo imprima el enésimo número primo,

Lo que he pensado es hacer algún tipo de recuento int y ++ ing cada vez que encuentre un primo, y cuando el recuento == n luego imprime ese número, pero no puedo entender cómo hacerlo aterrizarlo.

Answer 1

Acabo de agregar las líneas que faltan en tu propio proceso de pensamiento.

static int nthPrimeFinder (int n) {

    int counter = 1; // For 1 and 2. assuming n is not 1 or 2.
    int i = 2;
    int x = 2;
    int tempLength = n;

    while (counter <= n) {
        for (; i <= tempLength; i++) {
            for (x = 2; x < i; x++) {
                if (i % x == 0) {
                    break;
                }
            }
            if (x == i && counter < n) {
                //System.out.printf("/n%d is prime", x);
                counter++;
                if (counter == n) {
                    System.out.printf("/n%d is prime", x);
                    return counter;
                }
            }
        }
        tempLength = tempLength+n;
    }
    return 0;
}

Answer 2

Aunque muchas explicaciones correctas y detalladas están disponibles. pero aquí está mi implementación en C:

#include<stdio.h>
#include<conio.h> 

main()
{
int pk,qd,am,no,c=0;
printf("/n Enter the Number U want to Find");
scanf("%d",&no);
for(pk=2;pk<=1000;pk++)
{
am=0;
for(qd=2;qd<=pk/2;qd++)
{
if(pk%qd==0)
{
am=1;
break;
}}
if(am==0)
c++;
if(c==no)
{
printf("%d",pk);
break;
}}
getch();
return 0;
}

Answer 3

Estás tratando de hacer demasiado en el método principal. Debe dividir esto en partes más manejables. Escriba un método boolean isPrime(int n) que devuelva verdadero si un número es primo y falso de lo contrario. Luego modifique el método principal para usar isPrime.

Answer 4

Lógica a continuación: (código en python pero puedes entenderlo fácilmente):

def is_prime(n):
    if(n<=1):
        return 0
    if(n<4):
        return n
    if(n%2==0):
        return 0
    if(n<9):
        return n
    if(n%3==0):
        return 0
    f=5       #as you have already checked for the divisibility for 2 and 3 with n
    r=int(n**.5)

    while(f<=r):
        if(n%f==0):
            return 0
        if(n%(f+2)==0):  #only checking f+2 not incrementing f
            return 0
        f+=6     #remember this 6k+/-1 is a prime no. for k>=1 that why incrementing f by 6
                 # and we have also eliminated the possibilities of divisibility by 2 ,3...
    return n  #return n if its prime else return zero

¡¡Espero que esto ayude!!

Answer 5

Para calcular el n-ésimo primo, sé dos variantes principales.

La manera directa

Eso es contar todos los primos comenzando desde 2 a medida que los encuentre hasta que haya alcanzado el n ^th deseado.

Esto se puede hacer con diferentes niveles de sofisticación y eficiencia, y hay dos formas conceptualmente diferentes de hacerlo. El primero es

Probando la primalidad de todos los números en secuencia

Esto se lograría mediante una función de controlador como

public static int nthPrime(int n) {
    int candidate, count;
    for(candidate = 2, count = 0; count < n; ++candidate) {
        if (isPrime(candidate)) {
            ++count;
        }
    }
    // The candidate has been incremented once after the count reached n
    return candidate-1;
}

y la parte interesante que determina la eficiencia es la función isPrime .

La forma obvia para una verificación de primalidad, dada la definición de un número principal como un número mayor que 1 que es divisible solo por 1 y por sí mismo que aprendimos en la escuela¹, es

División de prueba

La traducción directa de la definición en código es

private static boolean isPrime(int n) {
    for(int i = 2; i < n; ++i) {
        if (n % i == 0) {
            // We are naive, but not stupid, if
            // the number has a divisor other
            // than 1 or itself, we return immediately.
            return false;
        }
    }
    return true;
}

pero, como pronto descubrirás si lo intentas, su simplicidad va acompañada de lentitud. Con esa prueba de primalidad, puede encontrar la 1000 ^th prime, 7919, en unos pocos milisegundos (aproximadamente 20 en mi computadora), pero encontrar la 10000 ^th prime, 104729, toma segundos (~ 2.4s), la 100000 ^th prime, 1299709 , varios minutos (alrededor de 5), el primer millonésimo, 15485863, tomaría aproximadamente ocho horas y media, el primo número diez millones, 179424673, semanas, y así sucesivamente. La complejidad del tiempo de ejecución es peor que la cuadrática - Θ (n² * log n).

Así que nos gustaría acelerar un poco la prueba de primalidad. Un paso que mucha gente toma es darse cuenta de que un divisor de n (distinto de n ) puede ser como máximo n/2 . Si usamos ese hecho y dejamos que el ciclo de división de prueba solo se ejecute a n/2 lugar de n-1 , ¿cómo cambia el tiempo de ejecución del algoritmo? Para los números compuestos, el límite inferior del bucle no cambia nada. Para números primos, el número de divisiones de prueba se reduce a la mitad, por lo que, en general, el tiempo de ejecución debe reducirse en un factor algo menor que 2. Si lo prueba, verá que el tiempo de ejecución se reduce casi a la mitad, por lo que casi todos se pasa tiempo verificando la primalidad de los primos a pesar de que hay muchos más compuestos que primos.

Ahora, eso no ayudó mucho si queremos encontrar el primer centenar, por lo que tenemos que hacerlo mejor. Tratando de reducir aún más el límite del bucle, veamos para qué números se necesita realmente el límite superior de n/2 . Si n/2 es un divisor de n , entonces n/2 es un número entero, en otras palabras, n es divisible por 2. Pero luego el bucle no pasa de 2, por lo que nunca (excepto para n = 4 ) alcanza n/2 . Muy bien, ¿cuál es el siguiente divisor más grande posible de n ? Por qué, n/3 por supuesto. Pero n/3 solo puede ser un divisor de n si es un entero, en otras palabras, si n es divisible por 3. Entonces el ciclo saldrá en 3 (o antes, en 2) y nunca alcanzará n/3 (excepto para n = 9 ). El siguiente divisor más grande posible ...

¡Espera un minuto! Tenemos 2 <-> n/2 y 3 <-> n/3 . Los divisores de n vienen en pares.

Si consideramos el par (d, n/d) de los divisores correspondientes de n , ya sea d = n/d , es decir d = √n , o uno de ellos, por ejemplo d , es más pequeño que el otro. Pero luego d*d < d*(n/d) = n y d < √n . Cada par de divisores correspondientes de n contiene (al menos) uno que no supera √n .

Si n es compuesto, su divisor no trivial más pequeño no excede √n .

De modo que podemos reducir el límite de bucle a √n , y eso reduce la complejidad del algoritmo en tiempo de ejecución. Ahora debería ser Θ (n ^1.5 * √ (log n)), pero empíricamente parece escalar un poco mejor, sin embargo, no hay datos suficientes para extraer conclusiones fiables de los resultados empíricos.

Eso encuentra la millonésima en alrededor de 16 segundos, la décima millonésima en apenas nueve minutos, y encontraría la centésima en aproximadamente cuatro horas y media. Eso todavía es lento, pero muy lejos de los diez años más o menos tomaría la ingenua división de prueba.

Como hay cuadrados de primos y productos de dos primos cercanos, como 323 = 17 * 19, no podemos reducir el límite para el ciclo de división de prueba debajo de √n . Por lo tanto, mientras permanezcamos en la división de prueba, debemos buscar otras formas de mejorar el algoritmo ahora.

Una cosa fácil de ver es que ninguna prima distinta a 2 es pareja, por lo que solo debemos verificar los números impares después de habernos ocupado 2. No obstante, eso no hace mucha diferencia, ya que los números pares son los más baratos de encontrar compuesto - y la mayor parte del tiempo todavía se gasta para verificar la primalidad de primos. Sin embargo, si miramos los números pares como divisores candidatos, vemos que si n es divisible por un número par, n mismo debe ser par, entonces (excepto 2) se habrá reconocido como compuesto antes de la división por cualquier número par mayor de 2 se intenta. Entonces, todas las divisiones por números pares mayores que 2 que ocurren en el algoritmo deben necesariamente dejar un resto distinto de cero. Por lo tanto, podemos omitir estas divisiones y verificar la divisibilidad solo por 2 y los números impares desde 3 hasta √n . Esto reduce a la mitad (no exactamente) el número de divisiones requeridas para determinar un número como primo o compuesto y, por lo tanto, el tiempo de ejecución. Ese es un buen comienzo, pero ¿podemos hacerlo mejor?

Otra gran familia de números son los múltiplos de 3. Cada tercera división que realizamos es por un múltiplo de 3, pero si n es divisible por uno de ellos, también es divisible por 3, y por lo tanto no hay división por 9, 15, 21. , ... que realizamos en nuestro algoritmo alguna vez dejaremos un resto de 0. Entonces, ¿cómo podemos saltear estas divisiones? Bueno, los números divisibles ni por 2 ni 3 son precisamente los números de la forma 6*k ± 1 . Comenzando desde 5 (dado que solo estamos interesados ​​en números mayores que 1), son 5, 7, 11, 13, 17, 19, ..., el paso de uno a otro alterna entre 2 y 4, que es lo suficientemente fácil, así que podemos usar

private static boolean isPrime(int n) {
    if (n % 2 == 0) return n == 2;
    if (n % 3 == 0) return n == 3;
    int step = 4, m = (int)Math.sqrt(n) + 1;
    for(int i = 5; i < m; step = 6-step, i += step) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

Esto nos da otra aceleración por un factor de (casi) 1.5, por lo que necesitaríamos aproximadamente una hora y media para alcanzar el primer centenar de millones.

Si continuamos esta ruta, el siguiente paso es la eliminación de múltiplos de 5. Los números coprimados a 2, 3 y 5 son los números de la forma

30*k + 1, 30*k + 7, 30*k + 11, 30*k + 13, 30*k + 17, 30*k + 19, 30*k + 23, 30*k + 29

entonces solo necesitaríamos dividir por ocho de cada treinta números (más los tres números primos más pequeños). Los pasos de uno a otro, comenzando desde 7, pasan por 4, 2, 4, 2, 4, 6, 2, 6. Eso es aún bastante fácil de implementar y produce otro aumento de velocidad por un factor de 1.25 (menos un poco para código más complicado). Yendo más lejos, los múltiplos de 7 serían eliminados, dejando 48 de cada 210 números para dividir por, luego 11 (480/2310), 13 (5760/30030) y así sucesivamente. Cada p primaria cuyos múltiplos son eliminados produce una aceleración de (casi) p/(p-1) , por lo que el retorno disminuye mientras que el costo (complejidad del código, espacio para la tabla de búsqueda para los pasos) aumenta con cada primo.

En general, uno se detendría pronto, después de eliminar los múltiplos de tal vez seis o siete números primos (o incluso menos). Aquí, sin embargo, podemos seguir hasta el final, cuando se han eliminado los múltiplos de todos los primos y solo se dejan los números primos como divisores candidatos. Ya que estamos buscando todos los primos en orden, cada primo se encuentra antes de que se necesite como un divisor candidato y luego se puede almacenar para uso futuro. Esto reduce la complejidad algorítmica a - si no he calculado mal - O (n ^1.5 / √ (log n)). A costa del uso del espacio para almacenar los números primos.

Con la división de prueba, eso es lo mejor posible, debes intentar dividir por todos los primos en √n o en la primera división de n para determinar la primalidad de n . Eso encuentra el primer millonésimo en aproximadamente media hora aquí.

Entonces que tal

Pruebas rápidas de primalidad

Los primos tienen otras propiedades teóricas de número que la ausencia de divisores no triviales que los números compuestos generalmente no tienen. Tales propiedades, si son rápidas de verificar, pueden formar la base de pruebas de primalidad probabilísticas o deterministas. La propiedad arquetípica se asocia con el nombre de Pierre de Fermat, quien, a principios del siglo XVII, encontró que

Si p es un primo, entonces p es un divisor de (a ^p -a) para todo a .

Esto - el llamado "pequeño teorema" de Fermat - es, en la formulación equivalente

Deje p ser un primo y no divisible por p . Entonces p divide un ^p-1 - 1.

la base de la mayoría de las pruebas rápidas de primalidad rápida (por ejemplo Miller-Rabin) y variantes o análogos de eso aparecen en aún más (por ejemplo, Lucas-Selfridge).

Entonces, si queremos saber si un número impar no demasiado pequeño n es primo (incluso los números pequeños son tratados eficientemente por división de prueba), podemos elegir cualquier número a (> 1) que no sea múltiplo de n , por ejemplo 2, y compruebe si n divide a ^n-1 - 1. Dado que ^{n-1 se} vuelve enorme, esto se hace de manera más eficiente comprobando si a^(n-1) ≡ 1 (mod n) , es decir, mediante exponenciación modular. Si esa congruencia no se cumple, sabemos que n es compuesta. Si se cumple, sin embargo, no podemos concluir que n es primo, por ejemplo 2^340 ≡ 1 (mod 341) , pero 341 = 11 * 31 es compuesto. Los números compuestos n tales que a^(n-1) ≡ 1 (mod n) se denominan pseudoprimas de Fermat para la base a .

Pero tales ocurrencias son raras. Dada cualquier base a > 1 , aunque hay un número infinito de pseudoprimas de Fermat para basar a , son mucho más raros que los primos reales. Por ejemplo, solo hay 78 pseudoprimas de Fermat de base 2 y 76 pseudoprimas de Fermat de base 3 por debajo de 100000, pero primos de 9592. Entonces, si uno elige un impar arbitrario n > 1 y una base arbitraria a > 1 y encuentra a^(n-1) ≡ 1 (mod n) , hay una gran posibilidad de que n sea ​​realmente primo.

Sin embargo, estamos en una situación ligeramente diferente, nos dan n y solo podemos elegir a . Entonces, para un compuesto impar n , ¿para cuántos a , 1 < a < n-1 puede a^(n-1) ≡ 1 (mod n) sostenerse? Desafortunadamente, hay números compuestos, números de Carmichael, de modo que la congruencia se mantiene para cada a primos de n . Eso significa que para identificar un número de Carmichael como compuesto con la prueba de Fermat, tenemos que elegir una base que es un múltiplo de uno de los divisores principales de n , es posible que no haya muchos de esos múltiplos.

Pero podemos fortalecer la prueba de Fermat para que los compuestos se detecten de manera más confiable. Si p es un primo impar, escriba p-1 = 2*m . Entonces, si 0 < a < p ,

a^(p-1) - 1 = (a^m + 1) * (a^m - 1)

y p divide exactamente uno de los dos factores (los dos factores difieren en 2, por lo que su mayor divisor común es 1 o 2). Si m es par, podemos dividir a^m - 1 de la misma manera. Continuando, si p-1 = 2^s * k con k impar, escriba

a^(p-1) - 1 = (a^(2^(s-1)*k) + 1) * (a^(2^(s-2)*k) + 1) * ... * (a^k + 1) * (a^k - 1)

entonces p divide exactamente uno de los factores. Esto da lugar a la fuerte prueba de Fermat,

Deje n > 2 ser un número impar. Escriba n-1 = 2^s * k con k impar. Dado cualquier a con 1 < a < n-1 , si

1. a^k ≡ 1 (mod n) o
2. a^((2^j)*k) ≡ -1 (mod n) para cualquier j con 0 <= j < s

entonces n es un primer probable fuerte (Fermat) para la base a . Una base fuerte compuesta a (Fermat) prima probable se llama pseudoprima fuerte (Fermat) para la base a . Los pseudoprimas de Fermat fuertes son incluso más raros que los pseudoprimeros de Fermat ordinarios, por debajo de 1000000, hay 78498 cebadores, 245 pseudoprimas de Fermat de base 2 y solo 46 pseudoprimas de Fermat de base 2 fuertes. Más importante aún, para cualquier compuesto impar n , hay a lo sumo (n-9)/4 bases 1 < a < n-1 para las cuales n es un fuerte Fermat pseudoprime.

Entonces, si n es un compuesto impar, la probabilidad de que n pase k pruebas fuertes de Fermat con bases elegidas al azar entre 1 y n-1 (límites exclusivos) es menor que 1/4^k .

Una prueba de Fermat fuerte toma O (log n) pasos, cada paso implica una o dos multiplicaciones de números con O (log n) bits, por lo que la complejidad es O ((log n) ^ 3) con la multiplicación ingenua [para n enorme, algoritmos de multiplicación más sofisticados pueden valer la pena].

La prueba de Miller-Rabin es la prueba de Fermat k-fold con bases elegidas al azar. Es una prueba probabilística, pero para límites suficientemente pequeños, se conocen combinaciones cortas de bases que dan un resultado determinista.

Las pruebas fuertes de Fermat son parte de la prueba determinante APRCL.

Es aconsejable preceder a tales pruebas con la división de prueba con los primeros pocos números primos pequeños, ya que las divisiones son comparativamente baratas y eliminan la mayoría de los compuestos.

Para el problema de encontrar la n ^th prime, en el rango donde es factible probar todos los números para la primalidad, existen combinaciones conocidas de bases que hacen que la prueba fuerte de Fermat múltiple sea correcta, de modo que se obtendría un resultado más rápido - O (n * (log n) ⁴ ) - algoritmo.

Para n < 2^32 , las bases 2, 7 y 61 son suficientes para verificar la primalidad. Usando eso, la prima número cien millones se encuentra en aproximadamente seis minutos.

Eliminando compuestos por divisores principales, el tamiz de Eratóstenes

En lugar de investigar los números en secuencia y verificar si cada uno es primo desde el principio, también se puede considerar el conjunto completo de números relevantes como una sola pieza y eliminar los múltiplos de un primo dado de una vez. Esto se conoce como el Tamiz de Eratóstenes:

Para encontrar los números primos que no excedan N

1. hacer una lista de todos los números de 2 a N
2. para cada k de 2 a N : si k aún no está tachado, es primo; tachar todos los múltiplos de k como compuestos

Los números primos son los números en la lista que no están tachados.

Este algoritmo es fundamentalmente diferente de la división de prueba, aunque ambos usan directamente la caracterización de divisibilidad de los primos, en contraste con la prueba de Fermat y pruebas similares que usan otras propiedades de primos.

En la división de prueba, cada número n está emparejado con todos los números primos que no excedan el menor de √n y el divisor principal más pequeño de n . Como la mayoría de los composites tienen un divisor principal muy pequeño, la detección de materiales compuestos es barata en promedio. Pero el ensayo de primos es costoso, ya que hay relativamente muchos primos por debajo de √n . Aunque hay muchos más compuestos que primos, el costo de los primos de prueba es tan alto que domina por completo el tiempo de ejecución general y hace que la división de prueba sea un algoritmo relativamente lento. La división de prueba para todos los números menores que N toma O (N ^1.5 / (log N) ²) pasos.

En el tamiz, cada compuesto n está emparejado con todos sus divisores principales, pero solo con aquellos. Por lo tanto, los números primos son números baratos, solo se miran al mismo tiempo, mientras que los compuestos son más caros, se tachan varias veces. Uno podría creer que dado que un tamiz contiene muchos más números "caros" que los "baratos", en general sería un mal algoritmo. Sin embargo, un número compuesto no tiene muchos divisores primos distintos: el número de divisores primos distintos de n está limitado por log n , pero por lo general es mucho más pequeño, el promedio del número de divisores primos distintos de los números <= n es log log n - por lo que incluso los números "caros" en el tamiz son en promedio no más (o apenas más) caros que los números "baratos" para la división de prueba.

Al clasificar hasta N , para cada primo p , hay Θ(N/p) múltiplos para tachar, por lo que el número total de cruces es Θ(∑ (N/p)) = Θ(N * log (log N)) . Esto produce algoritmos mucho más rápidos para encontrar los números primos hasta N que la división de prueba o la prueba secuencial con las pruebas de primalidad más rápidas.

Sin embargo, hay una desventaja para el tamiz, usa memoria O(N) . (Pero con un tamiz segmentado, que se puede reducir a O(√N) sin aumentar la complejidad del tiempo).

Para encontrar el n ^th prime, en lugar de los números primos hasta N , también existe el problema de que no se sabe de antemano qué tan lejos debe llegar el tamiz.

Este último puede ser resuelto usando el teorema del número primo. El PNT dice

π(x) ~ x/log x (equivalently: lim π(x)*log x/x = 1),

donde π(x) es el número de números primos que no exceden x (aquí y abajo, log debe ser el logaritmo natural, para las complejidades algorítmicas no es importante qué base se elige para los logaritmos). A partir de esto, se sigue que p(n) ~ n*log n , donde p(n) es el n ^th prime, y hay buenos límites superiores para p(n) conocidos a partir de un análisis más profundo, en particular

n*(log n + log (log n) - 1) < p(n) < n*(log n + log (log n)), for n >= 6.

Entonces uno puede usar eso como el límite de tamizado, no excede el objetivo lejos.

El requisito de espacio O(N) puede superarse mediante el uso de un tamiz segmentado. Entonces, puede grabar los números primos debajo de √N para el consumo de memoria O(√N / log N) y usar segmentos de mayor longitud (O (√N) cuando el tamiz está cerca de N).

Hay algunas mejoras fáciles en el algoritmo como se indicó anteriormente:

1. comience a tachar múltiplos de p solo en p² , no en 2*p
2. eliminar los números pares del tamiz
3. eliminar los múltiplos de primos pequeños adicionales del tamiz

Ninguno de estos reduce la complejidad algorítmica, pero todos reducen los factores constantes en una cantidad significativa (como en la división de prueba, la eliminación de múltiplos de p produce una aceleración menor para una p mayor y aumenta la complejidad del código más que para una p más pequeña).

Usando las dos primeras mejoras rinde

// Entry k in the array represents the number 2*k+3, so we have to do
// a bit of arithmetic to get the indices right.
public static int nthPrime(int n) {
    if (n < 2) return 2;
    if (n == 2) return 3;
    int limit, root, count = 1;
    limit = (int)(n*(Math.log(n) + Math.log(Math.log(n)))) + 3;
    root = (int)Math.sqrt(limit) + 1;
    limit = (limit-1)/2;
    root = root/2 - 1;
    boolean[] sieve = new boolean[limit];
    for(int i = 0; i < root; ++i) {
        if (!sieve[i]) {
            ++count;
            for(int j = 2*i*(i+3)+3, p = 2*i+3; j < limit; j += p) {
                sieve[j] = true;
            }
        }
    }
    int p;
    for(p = root; count < n; ++p) {
        if (!sieve[p]) {
            ++count;
        }
    }
    return 2*p+1;
}

que encuentra la primo centenaria, 2038074743, en aproximadamente 18 segundos. Este tiempo se puede reducir a unos 15 segundos (aquí, YMMV) almacenando los indicadores empaquetados, un bit por indicador, en lugar de como boolean , ya que el uso reducido de la memoria proporciona una mejor localidad de memoria caché.

Embalaje de las banderas, eliminando también múltiplos de 3 y utilizando movimientos de bits para un conteo más rápido y rápido.

// Count number of set bits in an int
public static int popCount(int n) {
    n -= (n >>> 1) & 0x55555555;
    n = ((n >>> 2) & 0x33333333) + (n & 0x33333333);
    n = ((n >> 4) & 0x0F0F0F0F) + (n & 0x0F0F0F0F);
    return (n * 0x01010101) >> 24;
}

// Speed up counting by counting the primes per
// array slot and not individually. This yields
// another factor of about 1.24 or so.
public static int nthPrime(int n) {
    if (n < 2) return 2;
    if (n == 2) return 3;
    if (n == 3) return 5;
    int limit, root, count = 2;
    limit = (int)(n*(Math.log(n) + Math.log(Math.log(n)))) + 3;
    root = (int)Math.sqrt(limit);
    switch(limit%6) {
        case 0:
            limit = 2*(limit/6) - 1;
            break;
        case 5:
            limit = 2*(limit/6) + 1;
            break;
        default:
            limit = 2*(limit/6);
    }
    switch(root%6) {
        case 0:
            root = 2*(root/6) - 1;
            break;
        case 5:
            root = 2*(root/6) + 1;
            break;
        default:
            root = 2*(root/6);
    }
    int dim = (limit+31) >> 5;
    int[] sieve = new int[dim];
    for(int i = 0; i < root; ++i) {
        if ((sieve[i >> 5] & (1 << (i&31))) == 0) {
            int start, s1, s2;
            if ((i & 1) == 1) {
                start = i*(3*i+8)+4;
                s1 = 4*i+5;
                s2 = 2*i+3;
            } else {
                start = i*(3*i+10)+7;
                s1 = 2*i+3;
                s2 = 4*i+7;
            }
            for(int j = start; j < limit; j += s2) {
                sieve[j >> 5] |= 1 << (j&31);
                j += s1;
                if (j >= limit) break;
                sieve[j >> 5] |= 1 << (j&31);
            }
        }
    }
    int i;
    for(i = 0; count < n; ++i) {
        count += popCount(~sieve[i]);
    }
    --i;
    int mask = ~sieve[i];
    int p;
    for(p = 31; count >= n; --p) {
        count -= (mask >> p) & 1;
    }
    return 3*(p+(i<<5))+7+(p&1);
}

encuentra el primo número cien millones en unos 9 segundos, que no es insoportablemente largo.

Hay otros tipos de tamices primarios, de particular interés es el Tamiz de Atkin, que explota el hecho de que ciertas clases de congruencia de primos (racionales) son compuestos en el anillo de enteros algebraicos de algunas extensiones cuadráticas de ℚ. Aquí no es el lugar para expandir la teoría matemática, basta decir que el Tamiz de Atkin tiene una menor complejidad algorítmica que el Tamiz de Eratóstenes y por lo tanto es preferible para grandes límites (para pequeños límites, un tamiz de Atkin no demasiado optimizado tiene mayor por encima y por lo tanto puede ser más lento que un tamiz Eratosthenes optimizado de forma similar). La biblioteca de primegen DJ Bernstein (escrita en C) está bien optimizada para números por debajo de 2 ³² y encuentra la centena de millones de primos (aquí) en aproximadamente 1,1 segundos.

La manera más rápida

Si solo queremos encontrar la n ^th prime, no hay un valor intrínseco para encontrar también todos los números primos más pequeños. Si podemos saltear la mayoría de ellos, podemos ahorrar mucho tiempo y trabajo. Dada una buena aproximación a(n) al n ^th prime p(n) , si tenemos una forma rápida de calcular el número de primos π(a(n)) no exceda a(n) , podemos tamizar un pequeño rango por encima o por debajo de a(n) para identificar los pocos primos faltantes o excesivos entre a(n) y p(n) .

Hemos visto una aproximación fácilmente computable bastante buena a p(n) anterior, podríamos tomar

a(n) = n*(log n + log (log n))

por ejemplo.

Un buen método para calcular π(x) es el método Meissel-Lehmer , que calcula π(x) en aproximadamente O(x^0.7) tiempo (la complejidad exacta depende de la implementación, un refinamiento por Lagarias, Miller, Odlyzko, Deléglise y Rivat le permite a uno calcular π(x) en O (x ^2/3 / log² x) tiempo).

Comenzando con la aproximación simple a(n) , calculamos e(n) = π(a(n)) - n . Según el teorema del número primo, la densidad de primos cerca de a(n) es aproximadamente 1/log a(n) , por lo que esperamos que p(n) esté cerca de b(n) = a(n) - log a(n)*e(n) y tamizaríamos un rango ligeramente mayor que log a(n)*e(n) . Para una mayor confianza de que p(n) está en el rango de tamizado, uno puede aumentar el rango por un factor de 2, por ejemplo, que casi seguramente será lo suficientemente grande. Si el rango parece demasiado grande, se puede iterar con la mejor aproximación b(n) en lugar de a(n) , calcular π(b(n)) f(n) = π((b(n)) - n . Típicamente, |f(n)| será mucho más pequeño que |e(n)| . Si f(n) es aproximadamente -e(n) , c(n) = (a(n) + b(n)) / 2 será una mejor aproximación a p(n) . Solo en el caso poco probable de que f(n) esté muy cerca de e(n) (y no muy cerca de 0), encontrar una aproximación suficientemente buena para p(n) que la etapa de cribado final se puede hacer en el tiempo comparable a la computación π(a(n)) convierte en un problema.

En general, después de una o dos mejoras a la aproximación inicial, el rango a ser tamizado es lo suficientemente pequeño para que la etapa de cribado tenga una complejidad de O (n ^ 0.75) o mejor.

Este método encuentra la prima número cien millones en aproximadamente 40 milisegundos, y la primo 10-12, 29996224275833, en menos de ocho segundos.

tl; dr: Encontrar el n ^th prime se puede hacer de manera eficiente, pero cuanto más eficiente lo desees, más matemáticas se verán involucradas.

Tengo el código de Java para la mayoría de los algoritmos discutidos here , en caso de que alguien quiera jugar con ellos.

¹ Observación adicional para las almas excesivamente interesadas: la definición de los números primos utilizados en las matemáticas modernas es diferente, aplicable en situaciones mucho más generales. Si adaptamos la definición de la escuela para incluir números negativos, entonces un número es primo si no es ni 1 ni -1 y divisible solo por 1, -1, sí mismo y su negativo, que define (para enteros) lo que hoy se llama un elemento irreducible de ℤ, sin embargo, para enteros, las definiciones de elementos primos e irreducibles coinciden.

Answer 6

Usar Java 8 parallelStream sería más rápido. A continuación está mi código para encontrar el número primo Nth

public static Integer findNthPrimeNumber(Integer nthNumber) {
    List<Integer> primeList = new ArrayList<>();
    primeList.addAll(Arrays.asList(2, 3));
    Integer initializer = 4;
    while (primeList.size() < nthNumber) {
        if (isPrime(initializer, primeList)) {
            primeList.add(initializer);
        }
        initializer++;
    }
    return primeList.get(primeList.size() - 1);
}

public static Boolean isPrime(Integer input, List<Integer> primeList) {
    return !(primeList.parallelStream().anyMatch(i -> input % i == 0));
}

@Test
public void findNthPrimeTest() {
    Problem7 inputObj = new Problem7();
    Integer methodOutput = inputObj.findNthPrimeNumber(100);
    Assert.assertEquals((Integer) 541, methodOutput);
    Assert.assertEquals((Integer) 104743, inputObj.findNthPrimeNumber(10001));
}

Answer 7

Veo que ha recibido muchas respuestas correctas y una muy detallada. Creo que no lo estás probando para números primos muy grandes. Y su única preocupación es evitar imprimir el número primo intermedio por su programa.

Un pequeño cambio en tu programa hará el truco.

Mantenga su lógica de la misma manera y simplemente extraiga la instrucción de impresión fuera del ciclo. Romper el bucle externo después de n números primos.

import java.util.Scanner;
/**
 * Calculates the nth prime number
 * @author {Zyst}
 */
public class Prime {
    public static void main(String[] args) {

        Scanner input = new Scanner(System.in);
        int n, 
            i = 2, 
            x = 2;

        System.out.printf("This program calculates the nth Prime number/n");
        System.out.printf("Please enter the nth prime number you want to find:");
        n = input.nextInt();

        for(i = 2, x = 2; n > 0; i++) {
            for(x = 2; x < i; x++) {
                if(i % x == 0) {
                    break;
                }
            }
            if(x == i) {
                n--;
            }
        }
        System.out.printf("/n%d is prime", x);

    }
}

Answer 8

java.math.BigInteger tiene un método nextProbablePrime (). Aunque supongo que esto es para criptografía, podrías usarlo para tu trabajo.

BigInteger prime = BigInteger.valueOf(0);
for (int i = 0; i < n; i++) {
    prime = prime.nextProbablePrime();
}
System.out.println(prime.intValue());

Answer 9

int counter = 0;

for(int i = 1; ; i++) {
    if(isPrime(i)
        counter++;

    if(counter == userInput) {
        print(i);
        break;
    }
}

Editar: Su función principal podría usar un poco de trabajo. Aquí hay uno que he escrito:

private static boolean isPrime(long n) {
    if(n < 2)
        return false;

    for (long i = 2; i * i <= n; i++) {
        if (n % i == 0)
            return false;
    }
    return true;
}

Nota: solo tiene que ir al sqrt (n) cuando se analizan los factores, por lo tanto, el i * i <= n

Answer 10

public class prime{
    public static void main(String ar[])
    {
      int count;
      int no=0;
      for(int i=0;i<1000;i++){
        count=0;
        for(int j=1;j<=i;j++){

        if(i%j==0){
          count++;
         }
        }
        if(count==2){
          no++;
          if(no==Integer.parseInt(ar[0])){
            System.out.println(no+"/t"+i+"/t") ;
          }
        }
      }
    }
}