Autor
|
Tema: Numeros Primos (Leído 2,769 veces)
|
AlbertoBSD
Programador y
Moderador Global
Desconectado
Mensajes: 3.705
🏴 Libertad!!!!!
|
Muy buen dia.
Busco un metodo 100% seguro para deterinar si un numero dado es primo o no.
Es el metodo que estoy usanfo como lo indica wikipedia es dividir el numero dado entre todos los numeros primos que ya tengo guardados que sean menores o iguales a la raiz del numero dado y si en algun momento el resto de la divicion es 0 entonces el numero no es primo.
Para hacer mas eficiente el trabajo tengo guardadas los cuadrados n^2 en una tabla y cuando pregunto por un numero N solo hago una busqueda binaria y retorno el numero n mas cercano.
Cabe mencionar que ahorita apenas llevo numeros de hasta 7 bytes.
La pregunta aqui es.
¿Hay uno que sea mas rapido y con la misma certeza?
|
|
« Última modificación: 10 Mayo 2016, 02:16 am por AlbertoBSD »
|
En línea
|
|
|
|
|
AlbertoBSD
Programador y
Moderador Global
Desconectado
Mensajes: 3.705
🏴 Libertad!!!!!
|
Si te interesa aprender la base consulta https://en.wikipedia.org/wiki/Fermat_primality_testEl test de primalidad de Fermat es el core de estos algoritmos, se basa en que un número es primo si a toda base coprima con p le corresponde el elemento identidad a través del índice totient(p). Buen dia. ya he implememtado el test de primalidad de fermat y el algoritmo mejoro notablemente. Ahora solo corro el test completo contra los probables primos. Luego le hecho un ojo mas a fondo a loa demas algoritmos. Primero quiero entender bien la base matematica de los mismos antes de aplicarlos al codigo. Saludos
|
|
|
En línea
|
|
|
|
kub0x
Enlightenment Seeker
Colaborador
Desconectado
Mensajes: 1.486
S3C M4NI4C
|
Me alegro de que lo pongas en práctica, es un tema muy apasionante. Miller-Rabin corre en tiempo polinomial, aunque lo que suelen recomendar es hacer varias rondas de Fermat y si el número parece primo pasarlo por Miller-Rabin. Otras implementaciones primero hacen trial division con una lista de primos considerables, lo pasan a Fermat y a Miller-Rabin, en fin, como más cómodo te sientas.
Ojo que si lo que buscas es hacer una criba de números primos, hay métodos más eficientes, lo único que necesitas una estructura auxiliar para ir guardando los números.
Saludos!
|
|
|
En línea
|
|
|
|
AlbertoBSD
Programador y
Moderador Global
Desconectado
Mensajes: 3.705
🏴 Libertad!!!!!
|
Detalles El algoritmo estaba funcionando bien pero su puso lento... el problema fue la multiplicacion, era algo ineficiente, lo mejore con multiplicacion modular y posteriomente volvio a ir lento, ahora era la exponenciacion, ya la optimize tambien ahora tendre que ver como se comporta. Por cierto cuantos testigos recomiendan para el Test de primalidad de fermat estoy usando 5 actualmente pero en wikipedia dicen que solo use 4. ¿Que opinan? Saludos!
|
|
|
En línea
|
|
|
|
kub0x
Enlightenment Seeker
Colaborador
Desconectado
Mensajes: 1.486
S3C M4NI4C
|
Detalles El algoritmo estaba funcionando bien pero su puso lento... el problema fue la multiplicacion, era algo ineficiente, lo mejore con multiplicacion modular y posteriomente volvio a ir lento, ahora era la exponenciacion, ya la optimize tambien ahora tendre que ver como se comporta. Por cierto cuantos testigos recomiendan para el Test de primalidad de fermat estoy usando 5 actualmente pero en wikipedia dicen que solo use 4. ¿Que opinan? Saludos! Sobre la exponenciación, te recomiendo que checkees https://en.wikipedia.org/wiki/Montgomery_modular_multiplication y si estás utilizando exponentiation by squaring mejor migra a éste. Revisa https://en.wikipedia.org/wiki/Modular_exponentiation también. Sobre los witness en Fermat, bueno hay una regla que indica que la mitad de la clase de residuos son witnesses, por lo tanto testigos de que 'n' es compuesto, como ves hay una alta probabilidad de acierto a la hora de testear si n es compuesto (a no ser que sea un nº de carmichael), 5 en total estarían bien. También tienes el Lehmann test, que particularmente me gusta mucho por su simpleza y eficacia, se centra en el teorema de Cauchy el cúal afirma que existen elementos dentro del grupo cuyo orden multiplicativo es un factor primo del orden del grupo, por lo tanto si cogemos varios elementos del grupo (bases) y las elevamos a (p-1)/2 y no obtenemos 1 congruente, entonces no satisface el teorema, pero cuidado, que hay algo llamado raíz primitiva, cuyo orden multiplicativo en el grupo es el propio orden en el grupo, pero sólo hay una cantidad de totient(totient(p)), por lo tanto un par de vueltas de este test son muy RECOMENDABLES. Lehmann: http://en.algoritmy.net/article/48610/Lehmann-testhttps://en.wikipedia.org/wiki/Cauchy's_theorem_%28group_theory%29Saludos!
|
|
|
En línea
|
|
|
|
|
Mensajes similares |
|
Asunto |
Iniciado por |
Respuestas |
Vistas |
Último mensaje |
|
|
[Python 2.6] Funcion generadora de Numeros primos (5.761.455 primos en 19 seg)
Scripting
|
katas
|
2
|
9,849
|
10 Marzo 2010, 01:50 am
por Novlucker
|
|
|
NUMEROS PRIMOS
Programación C/C++
|
alviera
|
4
|
6,046
|
7 Diciembre 2010, 06:39 am
por N0body
|
|
|
NUMEROS PRIMOS
Programación C/C++
|
ALONSOQ
|
5
|
3,594
|
16 Junio 2012, 18:13 pm
por ALONSOQ
|
|
|
Numeros primos
Programación C/C++
|
Ander123
|
6
|
3,326
|
30 Agosto 2012, 21:15 pm
por leosansan
|
|
|
Sucesion parcial o completa entre numeros primos.
« 1 2 3 »
Criptografía
|
Usuario887
|
23
|
15,248
|
15 Febrero 2021, 23:56 pm
por Usuario887
|
|