Problema al generar primos en Delphi - Página 2

Casimiro Notevi · #21 13-10-2013

Sin ánimo de crear polémica

, pero me parece que mucho bla, bla, bla... pero no hay nada tangible, nada de código, documento, ninguna prueba de nada, etc.
Unicamente palabrería, que no dudo que sea correcto lo que se comenta, pero sin pruebas de nada

Victor Luis · #22 13-10-2013

Holas Nelson...

Gracias... revisare los enlaces que enviaste, respondiendo a tus preguntas:

1] Estos son los ultimos de mi anterior busqueda:
959.999.998.039 959.999.998.147 959.999.998.163 959.999.998.201 959.999.998.247 959.999.998.253 959.999.998.267 959.999.998.273 959.999.998.277 959.999.998.283 959.999.998.417 959.999.998.423 959.999.998.427 959.999.998.429 959.999.998.553 959.999.998.619 959.999.998.651 959.999.998.679 959.999.998.681 959.999.998.687 959.999.998.739 959.999.998.751 959.999.998.759 959.999.998.799 959.999.998.819 959.999.998.861 959.999.998.933 959.999.998.963 959.999.998.973 959.999.998.981 959.999.999.053 959.999.999.071 959.999.999.081 959.999.999.089 959.999.999.093 959.999.999.099 959.999.999.107 959.999.999.129 959.999.999.141 959.999.999.197 959.999.999.227 959.999.999.237 959.999.999.243 959.999.999.251 959.999.999.293 959.999.999.323 959.999.999.341 959.999.999.353 959.999.999.359 959.999.999.369 959.999.999.381 959.999.999.393 959.999.999.419 959.999.999.423 959.999.999.471 959.999.999.513 959.999.999.537 959.999.999.597 959.999.999.653 959.999.999.701 959.999.999.711 959.999.999.753 959.999.999.789 959.999.999.797 959.999.999.837 959.999.999.879 959.999.999.957 959.999.999.971 959.999.999.983 959.999.999.999
Estos los encontre usando Factoris:
1.110.000.000.023 3.810.000.000.011 3.810.000.000.013 30.810.000.000.047 30.810.000.000.067 300.810.000.000.017 300.810.000.000.077 3.000.810.000.000.013 30.008.100.000.000.007 300.081.000.000.000.019 3.000.810.000.000.000.121 30.008.100.000.000.000.029 300.081.000.000.000.000.031 3.000.810.000.000.000.000.157 30.008.100.000.000.000.000.061 300.081.000.000.000.000.000.001 3.000.810.000.000.000.000.000.029 300.810.000.000.000.000.000.000.000.247 300.810.000.000.000.000.000.000.000.000.000.017 300.810.000.000.000.000.000.000.000.000.000.000.000.151 300844950000000000000000000000000000000000000101 300844950000000000000000000000000000000000000000000031 300844950000000000000000000000000000000000000000000000000079 300844950000000000000000000000000000000000000000000000000169
300844950000000000000000000000000000000000000000000000000000000000000000000000000000000041
Como mi metodo sabe cuales son los base primos, los fui probando en Factoris y me indico que eran posibles primos ya que no encontro otros multiplos o divisores. Hasta donde se el metodo de Muller-Rabin solo es probabilistico, el metodo de Lucas-Lehmer es para primos de mersene y no comprendo a cabalidad lo que es en si, el metodo AKS indica que es mejor pero la formula o logaritmo que usa no lo he captado y no vi una pagina que use esto para verificar primos.
○ Como ya te indique anteriormente, para verificar que eran correctos los numeros primos que fui obteniendo con PRI-BASE los fui obteniendo con el metodo clasico, buscar si es multiplo de algun primo anterior hasta su raiz cuadrada, luego encontre paginas de donde se descargaban archivos de texto con numeros primos, los exporte a Excel y los compare; por ultimo los verifique con Factoris y en todos coincidian, esa es la seguridad que me dio para seguir adelante.

2] Mi equipo es Pentium-III con Windows-7 de 32 bits.

3] Probe en Delphi 7 luego en Visual Basic 6.0, este ultimo me parece mas manejable y se mas funciones por lo que uso Visual Basic. Encontre este foro o club y vi la aplicacion que adjuntaron, me parecio rapida hasta 100 mil pero al ponerlo que busque 1 millon de primos se volvio lentisimo, como dije buscar en un rango de 1.000 millones se encuentran unos 36 millones de numeros primos, mi aplicacion lo hace en 21-22 minutos, generalmente lo mandaba a buscar rangos desde 10 mil a 50 mil millones; pero en ciertos casos como ahora los busco de mil millones para sacar datos que me permitan crear unmetodo mas directo que el que uso.
○ Ayer me vino una idea y pense haberlo encontrado; pero no fue asi, solo encontre otro metodo similar a PRI-BASE, me faltan datos y eso busco, esta busqueda que pasara de 1 Billon es importante pues sacare datos que necesito. He calculado que entre los 14 a 17 billones los nuevos primos se reduciran a unos cientos, donde luego sera importante determinar los primos gemelos que aparecen y con todo esto estoy pensando mejorar mi metodo, no creo en si obtener una formula que pueda generar primos de manera directa; pero quien sabe.

4] Mi equipo es de 512 de RAM y 40 GB de disco duro, llevo mas de 1.000 archivos de numeros primos, los que voy comprimiendolos en grupos y luego los quemo en DVD, como te dije no necesito tenerlos siempre todos, hasta estas busquedas solo uso el primero, donde apenas se han activado 78.000 de los 20 millones de primos que contiene, lo que me durara para buscar rangos hasta mas de 10 billones, luego pondre el segundo archivo solamente y quitar el primero y asi continuar las busquedas.

5] Para entrar a esa competencia, me faltan evaluar unos datos y hacer tal vez algunas correcciones luego de llegar al cuatrillon, el primer dato importante son los primos desde 1 billon hasta 1 billon mil millones, buscare con rangos cortos para obtener la informacion que necesito evaluar.
Luego de esto no sera complicado llegar al cuatrillon pues como mencione el tiempo en si de buscar y sacar numeros primos en un rango de 1.000 millones es de 5-6 minutos, lo que tarda es al archivar los 36 millones de primos encontrados. Esta cantidad esta disminuyendo, ahora solo hay 35 millones, y segun veo habra un momento en que se producira un salto con una disminucion brusca de numeros primos, eso es importante para mi... Entonces del tiempo no me preocupo, se que se ira acelerando al haber pocos primos en adelante y cuando pase el cuatrillon, recien considerare estar en la competencia y determinar el tiempo en llegar a un numero primo con mas de 100 millones de digitos, claro si es que no antes logre encontrar el metodo mas directo que el que uso ahora como PRI-BASE, es eficiente y sencillo; pero creo que debe haber una logica directa de extraer los numeros primos.

Amigo Nelson, si lo miras desde mi logica verias que hay muchos valores coincidentes y que se repiten en las secuencias de los numeros primos, como no soy matematico, solo los apunto y lo dejo. Un ejemplo es que con 1 numero primo origen haciendo 2 calculos se genera los numeros primos base como lo hace mi metodo; pero son 2 calculos y al pasar el millon de digitos no se lo podra hacer pues las variables no soportan esta cantidad, por lo que por ahora me quedo con mi metodo que no tiene problema con eso y puede buscar primos infinitos... al menos hasta 100 millones de digitos.

6] No se de programas para instalar y que comprueben la primalidad de los numeros que obtengo. Como te dije ayer encontre una logica con el que haciendo un calculo selectivo me decia si es primo o no; pero resulto que era lo mismo que el metodo PRI-BASE, solo que este no necesita de los primos origen, de manera directa indica que tal numero no es primo y si fuera solo te daria entre el 50-60% de seguridad que lo es osea como lo hace Factoris pero sin ver si es multiplo de algun primo, si lo agregaria esto tal vez; pero a mi me interesa tener la base secuencial de todos los primos para encontrar el metodo directo. Por ahora y hasta donde he comprobado todo es correcto, no se si habra un fallo despues; la logica del metodo es diferente a los que he visto y tener una referencia.
Para simplificar la respuesta a tu pregunta te diria que si la Multiplicacion tiene un fallo en algun punto, si fuera asi creo que mi metodo lo tendria en algun momento dado.

Bueno Amigo.. otra vez gracias por los enlaces, los ire revisando, la informacion que compartes me hacen ver otras posibilidades de enfocar el tema de los numero primos...

Gracias...

Victor Luis · #23 13-10-2013

Holas Nelson...

Estaba revisando los enlaces que enviaste y lei sobre Riemann, que segun explican en palabras sencillas dicen que las posibilidades de saber si es primo un numero grande grande, esta en relacion al numero de digitos, osea n=digitos igual a n posibilidades. Para saber si este numero es primo
300844950000000000000000000000000000000000000000000000000000000000000000000000000000000041 que tiene 90 digitos en Factoris solo intente 11 veces y dijo que es posible primo, en otros fue casi a la primera y algunos mas de 40 intentos con la secuencia de mi metodo.

Creo haber entendido mal esto de Riemann y de ser asi, mil disculpas... espero me lo aclares si sabes de esto.... Gracias.

ecfisa · #24 13-10-2013

Hola.

Fuera de tópico, me pareció interesante leer un artículo sobre el mayor primo descubierto hasta la fecha. El logro es de un profesor de matemáticas (Curtis Cooper), es un primo de Mersenne (mersenne.org) y tiene nada menos que 17 millones de dígitos.

El artículo: Un matemático descubre el número primo mas grande...

Saludos

[nlsgarcia] · #25 13-10-2013

Victor Luis,

Cita:

Empezado por Victor Luis

...Mi equipo es Pentium-III con Windows-7 de 32 bits...512 de RAM y 40 GB de disco duro...

Es realmente notable esta configuración de hardware dado que Windows 7 requiere al menos 1 GB de RAM y para este tipo de cálculos se requiere de un mejor hardware.

Cita:

Empezado por Victor Luis

...Probe en Delphi 7 luego en Visual Basic 6.0, este ultimo me parece mas manejable y se mas funciones por lo que uso Visual Basic...

Pregunto: ¿Has considerado utilizar Delphi 7 para lograr un implementación más optima de tu algoritmo?, Delphi 7 es en todos los sentidos muy superior a VB6.

Cita:

Empezado por Victor Luis

...No se de programas para instalar y que comprueben la primalidad de los números que obtengo...

Revisa el link que te indique (PARI/GP home) en el Msg #20.

Cita:

Empezado por Victor Luis

...no soy matemático...

Pregunto: ¿Has considerado solicitar apoyo en la escuela de matemáticas de alguna universidad de tu localidad para mejorar y validar tu método?.

Cita:

Empezado por Victor Luis

...el método de Miller–Rabin solo es probabilístico...

Es correcto, pero puede ser determinístico, revisa esta información:

Cita:

Empezado por Wikipedia

...The Miller–Rabin algorithm can be made deterministic by trying all possible a below a certain limit. The problem in general is to set the limit so that the test is still reliable...

Tomado de: http://en.wikipedia.org/wiki/Miller%...primality_test

Revisa este link :

Cita:

Test de primalidad de Miller-Rabin : http://es.wikipedia.org/wiki/Test_de...e_Miller-Rabin

Cita:

Empezado por Victor Luis

...el método de Lucas–Lehmer es para primos de Mersenne...no comprendo a cabalidad lo que es en si...

Un número M es un número de Mersenne si es una unidad menor que una potencia de 2, es decir M = 2^n-1.

Revisa este link :

Cita:

Número primo de Mersenne : http://es.wikipedia.org/wiki/N%C3%BA...mo_de_Mersenne

Cita:

Empezado por Victor Luis

...el método AKS indica que es mejor...

Es correcto, dado que es un algoritmo determinista y comprueba en tiempo polinómico si un número natural es primo o compuesto.

Revisa este link :

Cita:

Test de primalidad AKS : http://es.wikipedia.org/wiki/AKS

Cita:

Empezado por Victor Luis

...Riemann...las posibilidades de saber si es primo un número grande...esta en relación al número de dígitos...

Revisa estos links :

Cita:

Hipótesis de Riemann : http://es.wikipedia.org/wiki/Hip%C3%B3tesis_de_Riemann

La Hipótesis de Riemman para jóvenes estudiantes : http://www.lsi.upc.edu/~argimiro/mypapers/newspapers/rieman4bachi.html

Cita:

Empezado por Victor Luis

...el método que uso y analizo ahora...es simple...un niño de primaria podría hacerlo sin calculadora...

Cita:

Empezado por Victor Luis

...Con la explicación dada sera fácil que lleguen al metodo...

Cita:

Empezado por Casimiro Notevi

...Sin ánimo de crear polémica...no hay nada tangible...sin pruebas de nada...

Pregunto:

1- ¿Cuantas líneas efectivas tiene tu código en VB6?.

2- ¿Cuantos pasos requiere tu método para hallar un número primo?.

3- ¿Puedes describir tu algoritmo en pseudocódigo para tener una mejor idea del mismo?.

4- ¿Por que no lo publicas a nivel académico para validar el mismo?, según comentas es muy efectivo y requiere pocos recursos computacionales.

Espero sea útil

Nelson.

Casimiro Notevi · #26 13-10-2013

No me creo nada

Victor Luis · #27 14-10-2013

Holas Nelson...

Para comenzar las ultimas intervenciones en este tema del foro, dire que inicie dando una sugerencia sobre el metodo utilizado, ya que el TEMA es "PROBLEMA AL GENERAR NUMEROS PRIMOS". Si hay un problema, lo que corresponde es orientar y sugerir alternativas de solucion y no solo poner codigo como piden y si no creen nada, pues problema de cada uno, no busco eso, solo compartir ideas. De que sirve publicar el codigo con la secuencia directa para extraer los numeros base de la criba de Eratostenes, si hay muchos no primos a depurar, necesita de todos los primos que se encuentren y a lo largo la busqueda sera eterna? es lo mismo que el metodo clasico... en si no ayudamos al problema planteado. Como les indique, modifiquen al codigo que publico Nelson, Sumen +2 y luego +4 y asi hasta el rango que quieran y de los numeros extraidos depuren los no primos sacando sus divisores primos. Con esto aceleraran el proceso y sera optimo hasta 100.000.0000.0000 luego tendran que dejar procesando dias para llegar un poco mas.

Respondiendo a tus preguntas Nelson:

◘ Se que debo actualizar mi equipo y lo hare; pero otro objetivo es demostrar que no se precisa de muchos ordenadores para buscar numeros primos, cuando busque numeros mas grandes sera notorio, ya que seguire usando un ordenador para esto.
○ Delphi 7 que instale esta en ingles y el hecho de poner punto y coma al final de cada linea y declarar correctamente las variables, que no digo que sea malo, son las razones por lo que lo pase a Visual Basic; tambien lo tengo en VBA Excel que busca en un tiempo similar al de VB. En si como no uso calculos complejos, no le veo la necesidad de programarlo en otro lenguaje, lo que por ahora me interesa es reducir el tiempo que tarda en archivar los numeros primos encontrados, si los archivo de poco a poco, tarda mas, por eso los archivo de rangos de mil millones; creo que es asi no mas por la cantidad de primos a archivar o tu que opinas al respecto...?
○ De pedir colaboracion a escuela de matematicas o en la universidad, lo haria despues de obtener y analizar los datos que necesito. Ahora ya llegue al Billon y estos sacando estos datos con busquedas de rangos menores, lo mismo hare alllegar al cuatrillon, luego de eso estara definido mi metodo. Como lo esperaba ha habido un significativo descenso de la cantidad de primos encontrados y el tiempo se ha reducido, lo que me indica que voy por buen camino.

◘ Sobre el Codigo de mi Metodo, no esta depurado para indicarte el numero de lineas y sobre los pasos son:

1º] Carga en variables el rango a buscar, en numero de ciclos a repetir los rangos y el limite para archivar los primos encontrados. Explicando un poco esto, uso un Rango de 50.000.000 osea buscara desde donde se quedo la ultima vez hasta sumado este rango; como es poco indico que repita varios ciclos, por ejemplo 20 ciclos de este rango para buscar en 1.000.000.000 como un rango global. Al mismo tiempo indico luego de cuantos ciclos debera archivar todos los primos encontrados que se van guardando en un vector, con lo que creara un archivo de numeros primos.

2º] Inicia el Proceso de Busqueda por Ciclos-Rangos.
○ Carga en un vector los numeros base a los que digo casi primos, como te indique para un rango de 50 millones sacara unos 13.333.336 numeros base, el resto son no primos.

3º] Activa Primos (asi lo digo) ve desde el ultimo primo activado y revisa cuales mas activar. Con esto me refiero a que toma el numero primo que seguiria del archivo y si se va a activar, saca del numero primo una secuencia de no mas de 10 valores con los que depurara los no primos del vector con numeros base. Si no le corresponde activar, salta al siguiente paso; como ves no preciso tener todos los primos, solo los necesarios que son cada vez pocos.

4º] Depuracion de no primos, con las secuencia depura los no primos y pone en otro vector los que son numeros primos; como te dije los almaceno para archivarlos despues, ya que esto me reduce el tiempo de archivado. Hice la prueba archivando directo los que encuentra y archivando mas cantidad, lo ideal me parecio hacerlo luego de 20 ciclos de 50 millones de rango, osea una busqueda de 1.000 millones, donde con el archivado tarda 21-22 minutos.

5º] Guarda controles de la busqueda del rango, para saber desde donde continuar la siguiente busqueda del rango. Aparte guarda una copia de la ultima busqueda por si en medio proceso hay corte de energia, de modo que restablezca los ultimos valores y reinicie la busqueda desde ahi. Eso me paso cuando por error elimine varios archivos de primos y tambien de la papelera, donde solo guarde una copia de los archivos control y tube que volver a buscar primos desde ese limite, ahora no tengo ese problema.
Tambien controla un limite definido, de modo que almacena en fracciones multiplos los nuevos primos a encontrar que tengan mas de 18-24 digitos, de modo que siga la busqueda y no tenga problemas en buscar primos de millones de digitos, todavia no he llegado ahi; pero el control y la estructura esta definida.

6º] Termina la Busqueda e informa el Tiempo del proceso y luego Actualiza los Controles de Archivos Primos y de Secuencias, para informar cual es el Ultimo primo encontrados, el Total de primos encontrados hasta esa busqueda, cuantos primos se activaron y cual el ultimo primo activado. Son datos para mi analisis posterior, los que voy anotando en cada busqueda.

Bueno eson son los pasos del programa, en si son el 2º,3º y 4º.

◘ Me pides que describa el algoritmo, lo que no comprendo a que te refieres, no tengo una formula, solo un metodo donde realizo operaciones aritmeticas, tanto para activar y depurar. Te dire que hay numeros definidos y cantidades que se repiten, que aplicados a los numeros primos origen, hacen posible sacar estos numeros base y depurar los no primos.
○ Como te dije, encontre el modo de obtener estos numeros base donde hay primos; pero no podia depurar los no primos, por lo que lo deje; pero como eran pocos para evaluar volvi a revisar mis anotaciones, hice calculos y encontre secuencias definidas de cada numero primo, hacia calculos con potencias a un principio y luego encontre otro modo simple y directo de obtener estas secuencias. Estaba a punto de ir a descansar, probe una forma mas y ahi estaban los datos, se fue el sueño, lo aplique para depurar los no primos y exporte los primos a una hoja de Excel, los compare y todos coincidian. Luego busque hasta 100 millones archivandolos y los compare con los que tenia en Excel sacados con el metodo clasico y todos coincidian; lo ultimo hice un procedimiento que revise si alguno es multiplo con primos verificados inicialmente, tardo un tiempo; pero no encontro divisores primos hasta su raiz cuadrada. Al decir primos verificados inicialmente me refiero a que si se que el 2,3,5,7 son primos, comprobando con estos obtendre los siguientes y estos seran primos verificados, eso me dio la seguridad para continuar haciendo mejoras en mi codigo.

◘ Por ultimo, a tu pregunta de publicar a nivel academico, reitero que me faltan 2 controles, en este limite del billon que estoy ahora en eso y en el limite del cuatrillon, pasado esto estara mi codigo definido, para solo buscar y realizar una mejora a mi metodo con los datos que salgan de los analisis que haga.
Ya te los hare saber amigo, pues agradesco la informacion que adjuntas...

☼ Respecto a lo que dije, que un niño de primaria podria hacerlo sin calculadora, fue sin mala intension... hablando con mi madre que no hizo secundaria, le explicaba como obtenia los numeros base, lo entendio facilmente y sin papel ni calculadora me fue diciendo los posibles primos desde la cantidad que le indicaba.
De todos modos, mis disculpas si hay quienes lo toman a mal...

Victor Luis · #28 14-10-2013

Holas Amigo Nelson...

Pues el 1º Dato que debia controlar al pasar del billon esta bien, busque en un rango de mil millones osea hasta 1.001.000.000.000 y todos los encontrados son primos, aqui dejo los ultimos 100 antes de este limite:

1.000.999.997.341 1.000.999.997.357 1.000.999.997.369 1.000.999.997.449 1.000.999.997.471 1.000.999.997.479 1.000.999.997.507 1.000.999.997.521 1.000.999.997.533 1.000.999.997.537 1.000.999.997.579 1.000.999.997.597 1.000.999.997.629 1.000.999.997.633 1.000.999.997.689 1.000.999.997.693 1.000.999.997.737 1.000.999.997.743 1.000.999.997.749 1.000.999.997.761 1.000.999.997.797 1.000.999.997.807 1.000.999.997.929 1.000.999.997.941 1.000.999.997.951 1.000.999.997.981 1.000.999.998.023 1.000.999.998.043 1.000.999.998.169 1.000.999.998.191 1.000.999.998.203 1.000.999.998.287 1.000.999.998.319 1.000.999.998.391 1.000.999.998.409 1.000.999.998.413 1.000.999.998.463 1.000.999.998.473 1.000.999.998.499 1.000.999.998.517 1.000.999.998.521 1.000.999.998.527 1.000.999.998.529 1.000.999.998.539 1.000.999.998.613 1.000.999.998.619 1.000.999.998.641 1.000.999.998.643 1.000.999.998.697 1.000.999.998.731 1.000.999.998.751 1.000.999.998.787 1.000.999.998.827 1.000.999.998.829 1.000.999.998.839 1.000.999.998.857 1.000.999.998.941 1.000.999.998.983 1.000.999.998.991 1.000.999.998.997 1.000.999.999.009 1.000.999.999.033 1.000.999.999.067 1.000.999.999.123 1.000.999.999.133 1.000.999.999.163 1.000.999.999.189 1.000.999.999.201 1.000.999.999.217 1.000.999.999.271 1.000.999.999.303 1.000.999.999.343 1.000.999.999.357 1.000.999.999.361 1.000.999.999.421 1.000.999.999.427 1.000.999.999.471 1.000.999.999.501 1.000.999.999.513 1.000.999.999.541 1.000.999.999.547 1.000.999.999.579 1.000.999.999.613 1.000.999.999.619 1.000.999.999.621 1.000.999.999.627 1.000.999.999.631 1.000.999.999.679 1.000.999.999.693 1.000.999.999.711 1.000.999.999.729 1.000.999.999.799 1.000.999.999.871 1.000.999.999.873 1.000.999.999.877 1.000.999.999.889 1.000.999.999.897 1.000.999.999.913 1.000.999.999.943 1.001.000.000.017

[nlsgarcia] · #29 15-10-2013

Victor Luis,

Cita:

Empezado por Victor Luis

...De que sirve publicar el código con la secuencia directa para extraer los números base de la Criba de Eratóstenes, si hay muchos no primos a depurar...

No son números Primos Probables, son Números Primos, ese es el objetivo del Algoritmo de Eratóstenes.

En lo personal, he hecho pruebas comparativas entre el Algoritmo de Divisiones Sucesivas, el Algoritmo de Eratóstenes y el Algoritmo de Atkin y en un rango de 2 a 500.000.000, los archivos resultantes son similares (26.355.867 Números Primos), lo que varía es el tiempo de generación. En otra prueba realizada en un rango de 2 a 2.147.483.615, el Algoritmo de Eratóstenes genero 105.097.563 Números Primos los cuales fueron probados aleatoriamente sin encontrar ningún número compuesto en la secuencia.

Cita:

Empezado por Victor Luis

...y a lo largo la búsqueda sera eterna, es lo mismo que el método clásico...

El Algoritmo de Eratóstenes es muy eficiente en comparación al método de divisiones sucesivas, sin embargo hay métodos más modernos como el Algoritmo de Atkin, el cual correctamente implementado tiene una eficiencia computacional superior al Algoritmo de Eratóstenes.

Cita:

Empezado por Victor Luis

...no se precisa de muchos ordenadores para buscar números primos...

Depende de los objetivos a conseguir, revisa esta información:

Cita:

...El proyecto GIMPS resulta excepcionalmente eficaz en la búsqueda de grandes números primos. Fundado en 1996, ha encontrado los últimos 14 primos de Mersenne. En él participan unas 360.000 computadoras que juntas son capaces de realizar hasta 150 billones de cálculos por segundo...

Tomado de: http://www.abc.es/ciencia/20130206/a...302061759.html

Cita:

Empezado por Victor Luis

...Delphi 7 que instale esta en ingles y el hecho de poner punto y coma al final de cada linea y declarar correctamente las variables, que no digo que sea malo, son las razones por lo que lo pase a Visual Basic...

Entiendo, sin embargo a futuro, quizás sean más claras las ventajas de usar un lenguaje como Delphi 7.

Cita:

Empezado por Victor Luis

...el Código de mi Método, no esta depurado para indicarte el numero de lineas...Me pides que describa el algoritmo, lo que no comprendo a que te refieres, no tengo una formula, solo un método...

Entiendo tu punto de vista, sin embargo el siguiente comentario podría arrojar algo de luz sobre tu método:

Cita:

Empezado por Victor Luis

...hablando con mi madre que no hizo secundaria, le explicaba como obtenía los números base, lo entendió fácilmente y sin papel ni calculadora me fue diciendo los posibles primos desde la cantidad que le indicaba...

Quizás la idea es: publicar la misma explicación para poder comprender y validar tu algoritmo, aunque entiendo que tienes tus reservas.

Cita:

Empezado por Victor Luis

...de publicar a nivel académico...

Suerte

Espero sea útil

Nelson.

Victor Luis · #30 15-10-2013

Holas Nelson...

Pues debo retractarme o explicar mejor lo que dije... en si me referia a la Criba de Eratostenes donde se ponen secuencialmente los numeros naturales en 6 columnas y los numeros primos estarian en la 1º y 5 columna. Revise las direcciones que adjuntaste y lei el algoritmo de Eratostenes que marcando los multiplos desde el 2, los que quedan son numeros primos y con estos se marcan sus multiplos.

○ Si cargas un vector con numeros base parecido a Eratostenes como lo indique sumando +2 y +4 comenzando desde el 5 tendras:
5_7 11_13 17_19 23_25 29_31 35_37 41_43 47_49 51_53
Como ves hay muchos no primos a depurar; pero si lo exportas a una hoja de Excel en una sola columna
5
7
11
13
17
19
23
25
29
31
35
37
41
43
47
49
53
55
59
61
65
67
71
73
77
79
83
85
89
91
95
97

Veras que hay una secuencia fija para depurar los multiplos de cada numero primo, por ejemplo inicias con el 5 comenzando desde su 5º multiplo 5x5=25 que seria el 1º y su posicion en el vector es el [8]=25, el siguiente a depurar 2º es 3 datos o filas mas abajo [11]=35.
Yo los veo como grupo de multiplos a depurar, por eso digo 1º y 2º. Los siguientes multiplos del primo estan en las filas [18] y [21], para saber esto sumo 10 filas del 1º multiplo del anterior grupo [8]+10= [18] a este le sumo 3 filas 18+3= [21] y es el 2º multiplo del grupo.
Lo mismo sucede con el numero primo 7 donde el multiplo de inicio es 7x5=35 [11] a este le sumas +5 y sera el 2º multiplo del grupo y esta en [16]. Para el siguiente grupo sumas 11+14=[25] y 25+5= [30] y asi se marcan o depurar todos sus multiplos.
○ No se si aplicaste esto en el algoritmo de Eratostenes; pero para depurar esta secuencia, cada numero primo te indica en que fila o posicion estan sus multiplos, en lugar de cargar un vector con numeros secuencialmente y marcar por ejemplo del 5 → 10,15,20,25,30,35,40,45,50,55,60,...
◘ Ese era el segundo metodo que realice luego del metodo clasico, que desde luego es mas rapido, solo usas bucles para ir depurando, pues ya sabes donde estan los multiplos de cada numero primo, incluso puedes calcular la posicion del 1º multiplo, de modo que obtienes numeros primos sin usar If_Then, con este metodo reduje el tiempo para buscar primos en un rango de 1 millon de 42 seg a 2 seg.
► Sobre este metodo no he encontrado referencias, tu me diras si es parecido al algoritmo de Eratostenes o no. Lo malo es que tarda mucho, comparando con PRI-BASE que es mas selectivo y directo, lo hace en 1/3 de tiempo que el anterior.

◘ Tomare en cuenta las recomendaciones que me das y practicare un poco mas Delphi 7 y lo de publicar mi explicacion, la verdad no se donde, pues en algunos foros, solo recibes notas que piden publicar el codigo y demas tonterias donde no hay un poco de seriedad.

◘ Sobre el avance de mi metodo, te comento que el primer dato que tenia que evaluar, esta bien y ya obtengo numeros primos mas de 1 billon y los comprobe con factoris y dejo el enlace para los que quieran verlo en Youtube...

http://www.youtube.com/watch?v=-GUMPYAqa-o&feature=youtu.be

Estos son los ultimos primos encontrados y verificados:
1039999998781
1039999998853
1039999998899
1039999998901
1039999998907
1039999998937
1039999998949
1039999998979
1039999999001
1039999999019
1039999999021
1039999999033
1039999999063
1039999999067
1039999999069
1039999999097
1039999999177
1039999999217
1039999999271
1039999999343
1039999999351
1039999999373
1039999999393
1039999999421
1039999999427
1039999999471
1039999999481
1039999999483
1039999999499
1039999999513
1039999999523
1039999999559
1039999999561
1039999999607
1039999999631
1039999999651
1039999999699
1039999999711
1039999999721
1039999999723
1039999999751
1039999999777
1039999999783
1039999999817
1039999999847
1039999999853
1039999999867
1039999999891
1039999999963
1039999999981

Casimiro Notevi · #31 15-10-2013

Cita:

Empezado por Victor Luis

◘ Tomare en cuenta las recomendaciones que me das y practicare un poco mas Delphi 7 y lo de publicar mi explicacion, la verdad no se donde, pues en algunos foros, solo recibes notas que piden publicar el codigo y demas tonterias donde no hay un poco de seriedad.

Esto es un foro de programación delphi, se comparte conocimientos, trucos, etc. mediante el código fuente. Lo de las tonterías y poca seriedad, son las tuyas, que no haces más que hablar de tu maravilloso programa secreto en visual basic y nada más.

Así que, resumiendo, te aconsejo que practiques lo que criticas: menos tonterías y más seriedad, gracias.

[nlsgarcia] · #32 15-10-2013

Victor Luis,

Cita:

Empezado por Victor Luis

...No se si aplicaste esto en el algoritmo de Eratóstenes...

Te sugiero revisar el Algoritmo de Eratóstenes.

Cita:

Empezado por Victor Luis

...Sobre este método no he encontrado referencias...

Te sugiero revisar el Algoritmo de Atkin.

Cita:

Empezado por Victor Luis

...y lo de publicar mi explicación, la verdad no se donde, pues en algunos foros, solo recibes notas que piden publicar el código y demás tonterías donde no hay un poco de seriedad...

En el mundo de la ciencia y a nivel profesional se requiere poder demostrar el trabajo realizado y que este pueda ser verificable y repetible por otras personas para comprobar su veracidad y efectividad. Las dudas expresadas en este foro son ciertamente válidas y justificables en todo sentido y honestamente considero poco probable una reacción diferente en otro foro de programación o matemáticas.

Si esperas poder presentar tu trabajo a nivel académico debes tener una fuerte base matemática y en computación, haber revisado los métodos publicados sobre este tema, indicar claramente en que consiste tu algoritmo, cuales son sus ventajas sobre los métodos anteriores y ser capaz de demostrar todo lo sustentado en tus afirmaciones, el mundo académico es ciertamente muy exigente en este sentido.

Te sugiero considerar todo lo comentado en este hilo y nuevamente mucha suerte en tu proyecto

Espero sea útil

Nelson.

Casimiro Notevi · #33 15-10-2013

Cita:

Empezado por nlsgarcia

En el mundo de la ciencia y a nivel profesional se requiere poder demostrar el trabajo realizado y que este pueda ser verificable y repetible por otras personas para comprobar su veracidad y efectividad. Las dudas expresadas en este foro son ciertamente válidas y justificables en todo sentido y honestamente considero poco probable una reacción diferente en otro foro de programación o matemáticas.
Si esperas poder presentar tu trabajo a nivel académico debes tener una fuerte base matemática y en computación, haber revisado los métodos publicados sobre este tema, indicar claramente en que consiste tu algoritmo, cuales son sus ventajas sobre los métodos anteriores y ser capaz de demostrar todo lo sustentado en tus afirmaciones, el mundo académico es ciertamente muy exigente en este sentido.
Te sugiero considerar todo lo comentado en este hilo y nuevamente mucha suerte en tu proyecto

Espero sea útil

Nelson.

Es justo lo que yo quería decir, pero con palabras bonitas

Que quede claro, Victor Luis, que no tengo nada personal contra ti, saludos.

Victor Luis · #34 15-10-2013

Holas Nelson y Casimiro...

Me disculpo ante el Foro Delphi y en especial ante ustedes... creo que me excedi un poco pero no es por el foro ni sus organizadores; pero hubo algunos comentarios que estaban fuera de lugar por otros miembros del foro, que manifestaban que publique el codigo sino no te creemos y eso va contra mi manera de ser y mi personalidad, no me conocen, espero un dia si....

○ Se que es un Foro Delphi, el primer lenguaje que aprendi fue Basic en colegio, usando los Atari computer, despues de mucho tiempo todo era diferente y aprendi Pascal y de ahi Delphi con lo que hice varias aplicaciones. Luego consegui Visual Basic y medio me perdi; por lo que empece a usar VBA Excel para hacer programas para mi Laboratorio y despues copie elcodigo a Visual Basic, modifique algo y era casi lo mismo, lo que me resulto mas sencillo....
◘ Pero sera un compromiso... Intensificare mis conocimientos en Delphi... como dice Nelson es un leguaje eficiente... eso tambien lei de Java pero medio voy por ahi...

○ Respecto a lo que dice Casimiro de compartir conocimientos y trucos y mas.... estoy de acuerdo; pero no solo mediante la publicacion de codigo fuente. Si vieron, les comparti el metodo que para mi es simplicado y mejor que Eratostenes, les indique como depurar los multiplos de la secuencia extraida con las sumas +2 +4 y que los multiplos para mi estan en grupos de 2 multiplos, estos saltos o posiciones son propias para los multiplos de cada numero primo y se repiten.
◘ Con esto Casimiro creo estar aportando al foro y al tema en cuestion del Problema al Generar Numeros Primos, el tiempo del proceso se reducira significativamente y podra hacer busquedas de numeros mas grandes... La cosa esta en que quieren el codigo fuente y por ahora no lo tengo en Delphi, pues es un metodo que lo deje de usar porque encontre otros 3 metodos mejores y el 4º fue el que uso ahora...
○ Pero si tienen alguna duda al respecto... estoy predispuesto a brindar mi colaboracion como lo hace mi amigo Nelson...

○ Sobre el ultimo comentario de Nelson dire que lo se amigo...
Gracias por recordarmelo, no soy matematico y mis conocimientos de programacion son del promedio medio o regular y es esto lo que me motiva a seguir adelante.
◘ Un dia publicare mi metodo, luego de ajustar el 2º dato que me falta al pasar el cuatrillon, veran que es verificable y repetible, lo que si no creo poder exponer una formula como los que hay, que no los entiendo; pero estoy seguro que en base a esta logica surgiran formulas e ideas que mejoren la busqueda de numeros primos... al menos esa es mi espectativa.
Por ahora no puedo hacerlo presentar un metodo que esta desarrollado hasta el 95%, soy prudente en ello pues como bien dice Nelson "el mundo académico es ciertamente muy exigente en este sentido"

◘ Bueno amigos me ausentare un tiempo breve por asuntos de trabajo y no les molestare con mis tonterias... espero les vaya bien en el desarrollo del metodo...

NOTA. (para Nelson) Mi hermano Nelson Arteaga que actualmente radica en Puno-Peru tiene acceso a mi equipo y todos mis apuntes de los analisis realizados.
○ Un favor, si sabes de donde puedo descargar un Manual de Delphi 7 en español, te lo agradeceria....

[nlsgarcia] · #35 15-10-2013

Victor Luis,

Cita:

Empezado por Victor Luis

...donde puedo descargar un Manual de Delphi 7 en español...

La siguiente información esta en su mayoría en español con algunas excepciones en ingles.

Revisa estos Tutorials de Delphi:

Cita:

Tutorial Borland Delphi : http://www.programacionfacil.com/borland_delphi/start

Lenguaje Delphi : http://es.wikibooks.org/wiki/Lenguaje_Delphi

Curso de Delphi Básico : http://terawiki.clubdelphi.com/Delph...asico_pdf_.rar

Curso de Delphi Paso a Paso : http://terawiki.clubdelphi.com/Delph..._paso_pdf_.zip

Delphi para Novatos : http://terawiki.clubdelphi.com/Delph...tos__html_.zip

Delphi el Hijo de Pascal : http://terawiki.clubdelphi.com/Delph...ascal_pdf_.rar

Delphi al Límite : http://terawiki.clubdelphi.com/Delph...imite_pdf_.zip

Revisa estos Links:

Cita:

Delphi Basics : http://www.delphibasics.co.uk/ (Excelente como referencia del lenguaje)

A Beginner's Guide to Delphi Programming : http://delphi.about.com/od/beginners/a/delphicourse.htm (Excelente site para Delphi en general)

Revisa estos libros:

Cita:

La cara oculta de Delphi 4, Autor Ian Marteens : http://terawiki.clubdelphi.com/Delph...phi_4_pdf_.zip (Es un libro muy recomendado)

Borland Delphi 6 Developer's Guide, Autores: Steve Teixeira And Xavier Pacheco (Internet, es un libro avanzado en Ingles)

La Biblia de Delphi 7, Autor: Marco Cantu. (Internet, es un libro muy interesante en español)

Revisa el FTP del Club Delphi:

Cita:

Delphi : http://terawiki.clubdelphi.com/Delphi/

Nota: Cuando puedas trasladar el código de tu algoritmo de VB6 a Delphi 7, los tiempos de proceso en general disminuirán de forma considerable.

Suerte

Espero sea útil

Nelson.

Victor Luis · #36 18-10-2013

Holas Nelson...

Gracias, ya estoy revisando los enlaces o links que adjuntaste...

Antes de publicar el codigo y no lluevan criticas, me gustaria enviartelo a tu correo y le des una chekeada o mirada.... OK

[nlsgarcia] · #37 21-10-2013

Club Delphi,

Los siguientes programas son un Compendio de Cribas de Generación de Números Primos implementadas en Delphi:

Criba de Eratóstenes:

Código Delphi [-]program GeneratorPrimeNumbers;

{
Cálculo de Números Primos por el Algoritmo: Criba de Eratóstenes (Versión 2).
}

uses
  Windows, SysUtils, Classes, Dialogs;

var
   Limit, RLimit : Integer;
   i, j: Integer;
   Numbers: TBits;
   F : TextFile;
   NumberPrime : Integer;
   TI, TF: TDateTime;
   Mnsj : String;

begin

   repeat
      try
         Limit := StrToInt(InputBox('Generador de Números Primos',
                                    'Número Primo Máximo a Calcular:', '1000'));
      except
         Limit := 0;
      end;
   until (Limit >= 2) and (Limit <= 2147483615);

   TI := Now;

   try

      Numbers := TBits.Create;
      Numbers.Size := Limit+1;
      RLimit := Trunc(Sqrt(Limit));
      NumberPrime := 0;

      for i := 2 to RLimit do
         if not Numbers[i] then
            for j := i to (Limit div i) do
               Numbers[i*j] := True;

      FileMode := fmOpenWrite;
      AssignFile(F, 'NumberPrime.txt');
      Rewrite(F);

      for i := 2 to Limit do
         if not Numbers[i] then
         begin
            // Writeln(F, Format('%.10d',[i]));
            Writeln(F, i);
            Inc(NumberPrime);
         end;

   finally

      Numbers.Free;
      CloseFile(F);

   end;

   TF := Now - TI;

   ThousandSeparator := '.';
   DecimalSeparator := ',';

   Mnsj := Format('Con el Número %s como Límite, Se Generaron %s Números Primos en %s',
                 [FormatFloat('#,###,###,###,##0',Limit),
                  FormatFloat('#,###,###,###,##0',NumberPrime),
                  FormatDateTime('hh:mm:ss:zzz', TF)
                 ]);

   MessageBox(0, PChar(Mnsj), 'Algoritmo: Criba de Eratóstenes', MB_OK + MB_ICONINFORMATION);

end.

Criba de Atkin:

Código Delphi [-]program GeneratorPrimeNumbers;

{
Cálculo de Números Primos por el Algoritmo: Criba de Atkin Optimizada
}

uses
  Windows, SysUtils, Classes, Dialogs;

var
   Limit, RLimit : LongWord;
   i, j : Integer;
   n,k : LongWord;
   R1 : LongWord;
   R2 : LongWord;
   xStepsize : LongWord;
   y_limit : LongWord;
   s, min_y, yy : LongWord;

   Numbers : TBits;
   F : TextFile;
   NumberPrime : LongWord;
   TI, TF : TDateTime;
   Msg : String;

begin

   repeat
      try
         Limit := StrToInt(InputBox('Generador de Números Primos',
                                    'Número Primo Máximo a Calcular:', '1000'));
      except
         Limit := 0;
      end;
   until (Limit >= 2) and (Limit <= 2147483615);

   TI := Now;

   Numbers := TBits.Create;

   try

      Numbers.Size := Limit+1;
      RLimit := Trunc(Sqrt(Limit));
      NumberPrime := 0;

      // Inicio del cálculo de 3x^2 + y^2
      xStepsize := 3;
      y_limit := 0;
      n := 0;
      R1 := Trunc(Sqrt((Limit - 1) / 3));

      i := 0;
      while (i < 12 * R1) do
      begin
         xStepsize := xStepsize + i;
         y_limit := 12 * Trunc(Sqrt(Limit - xStepsize)) - 36;
         n := xStepsize + 16;
         j := -12;
         while(j < y_limit + 1) do
         begin
            n := n + j;
            Numbers[n] := not Numbers[n];
            Inc(j,72);
         end;

         n := xStepsize + 4;

         j := 12;
         while (j < y_limit + 1) do
         begin
            n := n + j;
            Numbers[n] := not Numbers[n];
            inc(j,72);
         end;
         inc(i,24);
      end;
      // Fin del cálculo de 3x^2 + y^2

      // Inicio del cálculo de 4x^2 + y^2
      xStepsize := 0;
      R1 := 8 * Trunc(Sqrt((Limit - 1) / 4)) + 4;

      i := 4;
      while (i < R1) do
      begin
         xStepsize := xStepsize + i;
         n := xStepsize + 1;

         if (xStepsize mod 3 <> 0) then
         begin
            R2 := 4 * Trunc(Sqrt(Limit - xStepsize)) - 3;
            j := 0;
            while (j < R2) do
            begin
               n := n + j;
               Numbers[n] := not Numbers[n];
               Inc(j,8);
            end;
         end
         else
         begin
            y_limit := 12 * Trunc(Sqrt(Limit - xStepsize)) - 36;
            n := xStepsize + 25;
            j := -24;
            while (j < y_limit + 1) do
            begin
               n := n + j;
               Numbers[n] := not Numbers[n];
               Inc(j,72);
            end;

            n := xStepsize + 1;

            j := 24;
            while (j < y_limit + 1) do
            begin
               n := n + j;
               Numbers[n] := not Numbers[n];
               inc(j,72);
            end;
         end;
         inc(i, 8);
      end;
      // Fin del cálculo de 4x^2 + y^2

      // Inicio del cálculo de 3x^2 - y^2
      xStepsize := 1;
      R1 := Trunc(Sqrt(Limit/2))+1;

      i := 3;
      while (i < R1) do
      begin
         xStepsize := xStepsize + (4 * i - 4);
         n := 3 * xStepsize;
         s := 4;
         if (n > Limit) then
         begin
            min_y := (Trunc(Sqrt(n - Limit)) shr 2) shl 2;
            yy := min_y * min_y;
            n := n - yy;
            s := 4 * min_y + 4;
         end
         else
            s := 4;

         j := s;
         while (j < 4 * i) do
         begin
            n := n - j;
            if (n <= Limit) and (n mod 12 = 11) then
               Numbers[n] := not Numbers[n];
            Inc(j,8);
         end;
         inc(i,2);
      end;

      xStepsize := 0;
      i := 2;
      while (i < R1) do
      begin
         xStepsize := xStepsize + (4 * i - 4);
         n := 3 * xStepsize;
         s := 0;
         if (n > Limit) then
         begin
            min_y := ((Trunc(Sqrt(n - Limit)) shr 2) shl 2) - 1;
            yy := min_y * min_y;
            n := n - yy;
            s := 4 * min_y + 4;
         end
         else
         begin
            n := n - 1;
            s := 0;
         end;

         j := s;
         while(j < 4 * i) do
         begin
            n := n - j;
            if (n <= Limit) and (n mod 12 = 11) then
               Numbers[n] := not Numbers[n];
            inc(j,8);
         end;
         inc(i,2);
      end;
      // Fin del cálculo de 3x^2 - y^2

      i := 5;
      while (i <= RLimit+1) do
      begin
         if Numbers[i] then
         begin
            k := i*i;
            while (k < Limit) do
            begin
               Numbers[k] := False;
               Inc(k,i*i);
            end;
         end;
         Inc(i,2);
      end;

      FileMode := fmOpenWrite;
      AssignFile(F, 'NumberPrime.txt');
      Rewrite(F);

      Numbers[2] := True;
      Numbers[3] := True;

      for i := 2 to Limit do
         if Numbers[i] then
         begin
            Writeln(F, i);
            Inc(NumberPrime);
         end;

   finally

      Numbers.Free;
      CloseFile(F);

   end;

   TF := Now - TI;

   ThousandSeparator := '.';
   DecimalSeparator := ',';

   Msg := Format('Con el Número %s como Límite, Se Generaron %s Números Primos en %s',
                 [FormatFloat('#,###,###,###,##0',Limit),
                  FormatFloat('#,###,###,###,##0',NumberPrime),
                  FormatDateTime('hh:mm:ss:zzz', TF)
                 ]);

   MessageBox(0, PChar(Msg), 'Algoritmo: Criba de Atkin', MB_OK + MB_ICONINFORMATION);

end.

Criba de Sundaram:

Código Delphi [-]program GeneratorPrimeNumbers;

{
Cálculo de Números Primos por el Algoritmo: Criba de Sundaram
}

uses
  Windows, SysUtils, Classes, Dialogs;

var
   Limit, RLimit : LongWord;
   i, j, k : LongWord;
   Numbers: TBits;
   F : TextFile;
   NumberPrime : LongWord;
   TI, TF: TDateTime;
   Mnsj : String;
   maxVal : LongWord;
   denominator : LongWord;
   Prime : LongWord;

begin

   repeat
      try
         Limit := StrToInt(InputBox('Generador de Números Primos',
                                    'Número Primo Máximo a Calcular:', '1000'));
      except
         Limit := 0;
      end;
   until (Limit >= 2) and (Limit <= 2147483615);

   TI := Now;

   try

      Numbers := TBits.Create;
      k := Limit div 2;
      Numbers.Size := k + 1;
      NumberPrime := 0;

      maxVal := 0;
      denominator := 0;

      i := 1;
      while(i < k) do
      begin
         denominator := (i shl 1) + 1;
         maxVal := (k - i) div denominator;
         j := i;
         while(j <= maxVal) do
         begin
            Numbers[i + j * denominator] := True;
            inc(j);
         end;
         inc(i);
      end;

      FileMode := fmOpenWrite;
      AssignFile(F, 'NumberPrime.txt');
      Rewrite(F);
      Writeln(F, 2);
      Inc(NumberPrime);

      Prime := 0;
      i := 1;
      while(i < k) do
      begin
         if not Numbers[i] then
         begin
            Prime := (i shl 1) + 1;
            Writeln(F, Prime);
            Inc(NumberPrime);
         end;
         inc(i);
      end;

   finally

      Numbers.Free;
      CloseFile(F);

   end;

   TF := Now - TI;

   ThousandSeparator := '.';
   DecimalSeparator := ',';

   Mnsj := Format('Con el Número %s como Límite, Se Generaron %s Números Primos en %s',
                 [FormatFloat('#,###,###,###,##0',Limit),
                  FormatFloat('#,###,###,###,##0',NumberPrime),
                  FormatDateTime('hh:mm:ss:zzz', TF)
                 ]);

   MessageBox(0, PChar(Mnsj), 'Algoritmo: Sieve of Sundaram', MB_OK + MB_ICONINFORMATION);

end.

Todas las anteriores implementaciones permite calcular con el Número 2.147.483.615 como cota límite, un máximo de 105.097.563 Números Primos en tiempos variables, sobre una máquina con un Procesador Phenom II X6 1090T, 4 GB RAM, 3 TB HDD y Windows 7 Profesional x32, como se muestra en la siguiente imagen a continuación:

El tiempo indicado en la imagen para los diferentes algoritmos es el tiempo total de proceso desde que inicia el cálculo hasta que finaliza la generación del archivo de 1.12 GB con los 105.097.563 Números Primos, lo cual implica que la verificación de los números primos: se hace en un tiempo menor al indicado.

Espero sea útil

Nelson.

Victor Luis · #38 22-10-2013

Holas Nelson...

La busqueda con el algoritmo de la criba de Eratostenes veo que es muy rapido... 2 minutos 25 segundos es un buen tiempo para un rango de poco mas de 2.000 millones...

○ Mi metodo PRI-BASE lo haria en 41 minutos, aunque ya encontre la forma de archivarlos en la mitad del tiempo que lo hacia, pero como dices el tiempo de busqueda es mas corto y lo que demora es archivar millones de numeros primos.
○ Una consulta al respecto, este tiempo es constante en cada busqueda del limite de 2.147.483.615 y por qué usan esta cantidad y no un limite entero... como 2.000 o 5.000 millones ?
Pregunto porque como indique el tiempo de mi metodo es constante, se cuando terminara no importa si busco en numeros grandes de mas de 18 o 24 digitos...

◘ Queria comentarte que intente poner el codigo en Delphi y he avanzado poco, creo que profundice mas VB, no encuentro las funciones compatibles como: Erase para inicializar un array, los Exponentes como 10^6, redondear hasta ciertos decimales y la funcion Format para dar formato a los numeros con puntos de mil o con decimales y me surge la duda si podre abrir los archivos de primos como otros con los Types que declare en Delphi, caso contrario tendria que iniciar desde 0 la busqueda y lo que queria es comparar los tiempos de las busquedas actuales...

◘ Por otro lado estoy analizando un metodo de Factorizacion para evaluar si un numero grande es primo o no, es una idea que me surgio y si resulta podria implementarlo al programa y ver que depure mayor cantidad de numeros grandes en menor tiempo.

Bueno amigo, para finalizar te dire que pronto tendre mi equipo actualizado con mas GB en el disco, mayor RAM y procesador, con lo que espero realizar busquedas con rangos mas grandes y reducir el tiempo del proceso....

Suerte y Gracias por la informacion que compartes....

[nlsgarcia] · #39 22-10-2013

Victor Luis,

Cita:

Empezado por Victor Luis

...este tiempo es constante en cada búsqueda del limite de 2.147.483.615 y por qué usan esta cantidad...

Cita:

Empezado por Victor Luis

...no encuentro las funciones...Erase para inicializar un array...los Exponentes...redondear...archivos...

Cita:

Empezado por Victor Luis

...estoy analizando un método de Factorización para evaluar si un numero grande es primo o no...

Te comento:

1- El tiempo de generación de números primos nunca es constante en ningún algoritmo, varia en función de la carga del computador a nivel de recursos, pero en general se mantiene con pocas variaciones. El limite de 2.147.483.615 esta fijado en función de la clase TBits, la cual tiene como tamaño máximo dicho límite, algo similar ocurre con los arrays en Delphi y C#.

2- En lo referente a las funciones equivalentes entre VB6 y Delphi 7 te sugiero revisar este link:

Cita:

Delphi Basics : http://www.delphibasics.co.uk/

3- Los métodos de factorización y primalidad no son adecuados para ser incluidos en un generador de números primos, dado que los tiempos se incrementarían notablemente, como ejemplo de un método de primalidad incluyo el de Miller-Rabin realizado en C# por tener el tipo BigInteger el cual facilita el uso de números enteros de gran tamaño, adecuado para su uso en algoritmos de números primos:

Código:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;
using System.Security.Cryptography;
using System.Windows.Forms;

namespace MillerRabin
{
    class Program
    {

        static bool IsProbablePrime(BigInteger source)
        {
            int certainty = 10;
            if (source == 2 || source == 3)
                return true;
            if (source < 2 || source % 2 == 0)
                return false;

            BigInteger d = source - 1;
            int s = 0;

            while (d % 2 == 0)
            {
                d /= 2;
                s += 1;
            }

            RandomNumberGenerator rng = RandomNumberGenerator.Create();
            byte[] bytes = new byte[source.ToByteArray().LongLength];
            BigInteger a;

            for (int i = 0; i < certainty; i++)
            {
                do
                {
                    rng.GetBytes(bytes);
                    a = new BigInteger(bytes);
                }
                while (a < 2 || a >= source - 2);

                BigInteger x = BigInteger.ModPow(a, d, source);
                if (x == 1 || x == source - 1)
                    continue;

                for (int r = 1; r < s; r++)
                {
                    x = BigInteger.ModPow(x, 2, source);
                    if (x == 1)
                        return false;
                    if (x == source - 1)
                        break;
                }

                if (x != source - 1)
                    return false;
            }

            return true;
        }

        static void Main(string[] args)
        {
            
            BigInteger Number;
            String AuxNumber;

            do
            {
               AuxNumber = Microsoft.VisualBasic.Interaction.InputBox("Número a Verificar Primalidad", 
                                                                       "Test de Primalidad MillerRabin", "");
               BigInteger.TryParse(AuxNumber, out Number);
               if (IsProbablePrime(Number))
                   MessageBox.Show("Es un Número Primo", "Test de Primalidad MillerRabin", 
                                   MessageBoxButtons.OK, MessageBoxIcon.Information);
               else if (AuxNumber != "")
                   MessageBox.Show("Es un Número Compuesto", "Test de Primalidad MillerRabin", 
                                   MessageBoxButtons.OK, MessageBoxIcon.Information);
            } while (AuxNumber != "");
            
        }
    }
}

El código anterior en C#, permite verificar la primalidad de un número por medio del algoritmo Miller-Rabin aplicado 10 veces por cada Primo Probable, a fin de garantizar su confiabilidad. Estoy revisando librerías que me permitan manejar grandes números enteros para trasladar el código a Delphi.

Pregunto: ¿Podrías explicar como manejas números enteros de 18 y 24 dígitos en VB6?

Espero sea útil

Nelson.

Victor Luis · #40 23-10-2013

Hola Amigo NELSON...

Realmente tienes una preparacion amplia y me quedo atras frente a vos, yo soy mas empirico y autodidacta... tengo un hermano mayor que estudio Ingenieria de Sistemas; sabe mucho pero como me conoce y dice siempre estoy queriendo descubrir la polvora, me ha enseñado algunas cosas pero la mayor parte de lo que se es por cuenta propia, pues como digo Todo se puede hacer en programacion y los programas no se equivocan, sino el programador....

◘ Respecto a lo que me comentas, de que el tiempo de generacion de numeros primos nunca es constante... no se si te refieres a la cantidad de primos encontrados lo cual es variable; pero conforme se avance esta cantidad disminuye paulatinamente. Pero si te refieres a tiempo en que se encuentran nuevos numeros primos en un rango dado, en mi caso es constante, buscando en 1.000 millones tardaba de 06:20 a 06:50 y ahora tarda entre 05:10 a 05:30 y no se si sigo mal... para mi esto es constante, no importa si busco en numeros de 12 digitos o de mas de 100 digitos, esto sigue siendo igual, claro que si aumentan o disminuyen unos segundos y eso no es constante, estoy equivocado....

◘ Referente al metodo de factorizacion, he leido un poco sobre los test de primalidad, no para copiar su metodo sino para entender hasta donde llego su logica... Es interesante por ejemplo el teorema de Fermat, la presipitacion de afirmar su descubrimiento que luego Euler comprobo las fallas o errores existentes, me falta leer mas de esa epoca; pero me pase al algoritmo AKS, el ultimo y eficiente que determina en tiempo polinominal (cosa que no me queda claro del todo) pero en una pagina indican que para la determinacion de un numero de 600 digitos emplearon unas 36 computadoras y el proceso tardo meses... su formula esta en "chino" para mi; pero ahora que avanzo y tengo mas numeros primos, se me ocurrieron dos metodos que los estoy analizando primero mediante una factorizacion directa y luego mediante una factorizacion multiple con otro enfoque, pues al evaluar numeros grandes las funciones aritmeticas no podran ser aplicadas.
☼ Se que debo estar cometiendo errores en mi expresion; pero com dije no soy matematico, es una idea que tengo, he probado unos calculos pero me falta corregirlos y ver que sea practico y lo elemental, debe ser simple, que aunque parezca ilogico es como tambien es mi metodo; pero funciona hasta ahora y ahora pude reducir el tiempo de busqueda a una (1/3) tercera parte de lo que lo hacia, por ejemplo buscar en un rango de 1.000 millones tardaba entre 21-22 min y ahora lo hace entre 7-8 min, incluido el archivado de los nuevos numeros primos, espero sea menor este tiempo luego que actualice mi equipo con mas RAM, procesador y Gigas de disco duro.

◘ Sobre tu pregunta de como manejo numeros de 18-24 digitos, es lo que pense cuando vi que mi metodo daba buenos resultados... y luego que, usando una variable Double o Decimal solo tienes para un monton de digitos; pero me cuestione si en verdad los calculos se haran de forma correcta, donde vi que desde 10 billones los ultimos digitos terminan siempre en "0" y eso me creo duda, no se, puedo estar equivocado al respecto; pero por lo simple de mi metodo, encontre un modo simple tambien, que funciona y su evaluacion final sera al pasar el cuatrillon y quintillon, donde al mismo tiempo me de datos para el analisis de la factorizacion que pienso hacer, por ahora amigo Nelson solo puedo decirte que en todo el proceso usare variables "double" y los numeros de mis calculos no pasaran de 21 a 24 digitos, osea esta variable es suficiente para mi... me preocupe por un rato e hice una verificacion inicial y esta bien.. ahora tal vez no entiendo a que te refieres con lo de "manejar numeros"... es como se hace, poner un valor a una variable y realizas calculos con ella... bueno no comprendo bien tu pregunta al respecto; pero te dije como lo estoy haciendo pero para estar seguro debo pasar con buenos resultados el cuatrillon, osea primos de mas de 24 digitos.

► Sobre el metodo de factotizacion, es una idea donde solo hice unos calculos que podrian resultar, las ecuaciones matematicas estan fuera de mi alcance, por lo que intento un metodo simple de acuerdo a mi conocimiento...

► Sobre el codigo a publicar, no avance nada, me parece ilogico pues ya mejore el rendimiento con VB; pero me dices que seria mas eficiente en Delphi... puede ser y no te contradigo, solo que como lo veo yo el tiempo se reducira y quedara estable entre 5 y maximo 6 minutos en cada busqueda de un rango de 1.000 millones, es mayor al algoritmo de Eratostenes; pero con mi equipo actualizado espero disminuya uno o dos minutos mas.

Bueno... Gracias por el enlace, esta en ingles y lo traducire... del codigo fuente que publicaste poco se de Java y peor C+, estoy actualizandome en Delphi 7, veo lo util de su compilador para evitar errores en la ejecucion, en lo que le supera a VB....
☼ Evitare no ser tan extenso; pero trato de explicarme de la forma mas clara y simple que puedo..... OK

Temas Similares
Tema	Autor	Foro	Respuestas	Último mensaje
11 millones de números primos	ixMike	La Taberna	15	06-10-2013 00:00:37
Suma de dígitos primos - Simplificar código	Subliminalz	Varios	3	12-06-2013 00:00:22
Ayuda con numeros primos	Jcn	Varios	4	28-05-2013 01:39:20
Como obtengo numeros primos ?	llSnakell	Varios	13	05-10-2011 03:56:09
Promedio.. digitos primos ..	luisito2011	Varios	3	07-05-2011 02:54:02