Post by SergioOn Thu, 20 Jul 2006 14:54:33 +0200, "Jorge S. de Lis"
Post by Jorge S. de LisNecesito ayuda.
Me parece un intervalo demasiado exagerado como para probarlos uno a
uno. ¿Alguien conoce alguna regla que me permita saberlo? (sólo el
número, no cuáles son).
Me temo que no, que nadie la conoce :-)
A priori, el número de primos comprendido entre dos enteros m y n
es bastante imprevisible. La única aproximación factible es, ni más
ni menos, que contarlos. Ahora bien, como has accedido a enviar
un mensaje a este newsgroup, doy por supuesto que tienes acceso
a un ordenador digital. En tal caso, contar los números primos
entre 1000 y 3000 es sencillo, en cualquier lenguaje de programación
de alto nivel se hace un programa para ello en dos patadas.
Puede haber mejores o peores algoritmos, si bien, si sólo pretendemos
llegar a un número tan pequeño como 3000, la aproximación más
trivial es perfectamente válida y en cualquier computador
contemporáneo tardará un tiempo muy breve: basta iterar sobre todos
los números entre 1000 y 3000 y, para cada uno de ellos, tratar de
dividirlo por todos los enteros entre 2 y la raíz cuadrada del número.
Si hallamos un divisor, no es primo.
Una mejora obvia es ir almacenando una lista de los primos que
vamos encontrando y tratar de dividir los nuevos candidatos
solamente entre los números primos menores que él. Si es divisible por
algún número distinto de sí mismo y la unidad que no sea primo,
también será divisible por los factores primos de dicho número, de
modo que no tiene sentido intentarlo con números compuestos salvo
por simplicidad y rapidez de implementación del algoritmo ( un momento
versus un poquito más). También se puede aplicar un procedimiento
de criba de eratóstenes, para determinar todos los primos que deseas,
o como paso inicial para un cierto subconjunto inicial de los
candidatos, cosa que eliminará muchas divisiones inútiles.
Ahora bien, aunque no conocemos ninguna forma de determinar cuántos
primos existen en un pequeño intervalo numérico, sí sabemos cómo se
comporta el número de primos cuando vamos considerando intervalos
mayores, donde las irregularidades de la frecuencia de primos en los
sucesivos tramos se van compensando en favor de una tendencia general.
Como seguramente sabes, se suele llamar pi a la función que , para
cada n, nos da el número de primos menor o igual que n. Se tiene que
pi(n) es aproximadamente n / ln n, y, notablemente, que el límite
cuando n tiende a infinito de pi (n) / ( n / ln n) es 1 ( de la Vallèe
Poussin y Hadamard, 1896). Una aproximación aún mejor a la
función pi que nos permite estimar el número de primos en un tramo
es 1 + SUMA en k, k=1, infinito ( 1 / ( k zeta(k+1) * (log n)^k / k!
),
con zeta representando la función zeta de Riemann.
Espero que eso ayude. Si no sueles programar y quieres, coméntalo
y te escribo aquí un programilla diminuto en C que cuenta el número
de primos, como te digo es brevísimo.
Saludos, S.
Añadiendo a lo que te ha dicho Sergio, se me ocurren otras dos posibilidades
para contarlos:
i) Criba de Eratóstenes. Hazte una tabla con los números del 1001 al 3000, y
tacha el segundo, cuarto, .... A continuación elimina el primer múltiplo de
3, y a partir de él ve tachando el tercero. Luego lo mismo con 5, 7, 11, 13,
17, 19, 23, 29, 31, 37, 41, 43, 47 y 53, que son todos los primos menores
que rq(3000) (esto supongo que enlaza con tu pregunta anterior). Cuando
hablo de tachar el tercero, el quinto, etc..., naturalmente se cuentan los
que ya están tachados, y si toca tachar uno que ya lo está, no se hace nada.
Luego solo hay que contar los sobrevivientes.
Esto se puede implementar muy fácilmente. Normalmente se consideran solo los
impares y se utiliza un bit para cada uno, poniedolos en principio a 1, y
pasandolos a 0 cuando se tachan. Pero para números de este orden,
posiblemente no compense, con utilizar un array de enteros sería suficiente.
No entro en más detalles de programación, porque la tengo un poco oxidada,
pero un programa muy sencillo y 'ad hoc', no general, se reduce simplemente
a 14 bucles for ... next, por ejemplo.
ii) Utilizar el principio de inclusiones y exclusiones. De los 2000 números,
descontamos los 1000 múltiplos de 2, los 2000/3 múltiplos de 3 (ojo a los
detalles), etc.... Como los múltiplos de 6 = 2*3, 10 = 2*5, 14 = 2*7, 15 =
3*5, ... se han descontado dos veces, hay que sumarlos una. Pero entonces
hay que descontar. Pero los múltiplos de 2*3*5 los acabamos de sumar tres
veces no una, por lo que habrá que descontarlos 2, etc...
Si se trata de una práctica de programación, indudablemente la solución i)
debe ser la mejor.
Para que puedas comprobar, hay 262 primos entre 1000 y 3000.
--
Saludos,
Ignacio Larrosa Cañestro
A Coruña (España)
***@mundo-r.com