Iniciar sesiónCerrar
Correo:
Contraseña:
Entrar
Recordar sesión en este navegador
Iniciar sesiónIniciar sesiónCrear cuentaCrear cuenta
LWP » Foros » Algoritmia » un problema matemático

Algoritmia - un problema matemático

Volver
Nuevo Tema
<<>>
 
Vista:

un problema matemático

Publicado por kern (2 intervenciones) el 20/12/2001 16:20:34
No se si alguno de vosotros sabrá de matracas, pero yo no, y tengo un problemo. Tengo que programar un algoritmo para hashing que me encuentre el número primo más próximo inferiormente a un entero dado (que no va a ser precisamente pequeño).

p.e: tengo una tabla de 8.000.000 de elementos. Pues tengo que encontrar el mayor primo n que cumpla n<8.000.000.

El caso es que la criba de Eratóstenes no me parece una buena solución, porque el problema va de hashing, y en un algoritmo O(1), perder mucho tiempo en encontrar un primo... Bueno, no se. Si algún avezado programador-matemático me puede ayudar...

salu2.kern
Valora esta pregunta
Me gusta: Está pregunta es útil y esta claraNo me gusta: Está pregunta no esta clara o no es útil
0
Responder
Imágen de perfil de Alejandro

Búsqueda eficiente del primo más cercano

Publicado por Alejandro (307 intervenciones) el 27/02/2024 23:09:08
Kern, entiendo que estás buscando un algoritmo eficiente para encontrar el número primo más cercano inferior a un entero dado. La criba de Eratóstenes puede ser innecesariamente costosa en términos de tiempo para este propósito específico.

Una alternativa más eficiente es utilizar el concepto de criba de Eratóstenes pero de manera invertida. Puedes verificar si un número es primo utilizando la división por primos conocidos, evitando así la necesidad de generar todos los primos hasta la raíz cuadrada del número en cuestión.

Aquí hay un ejemplo de cómo podrías implementar esto en pseudocódigo:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
Función esPrimo(n: Entero) -> Booleano
    Si n <= 1
        Devolver Falso
    Fin Si
 
    Para cada primo conocido p desde 2 hasta la raíz cuadrada de n
        Si n es divisible por p
            Devolver Falso
        Fin Si
    Fin Para
 
    Devolver Verdadero
Fin Función
 
Función encontrarPrimoAnterior(n: Entero) -> Entero
    Para i desde n-1 hasta 2 de manera decreciente
        Si esPrimo(i)
            Devolver i
        Fin Si
    Fin Para
 
    // Si llegamos aquí, no se encontró un primo inferior. Puede manejar este caso según tus necesidades.
    // Por ejemplo, podrías devolver un valor predeterminado o lanzar una excepción.
 
Fin Función

Este enfoque utiliza la prueba de divisibilidad solo con primos conocidos y va de manera descendente desde el número dado hasta encontrar el primo inferior más cercano.

Ten en cuenta que para algunos casos límite con números muy grandes, aún podría llevar tiempo encontrar el primo más cercano. Sin embargo, este enfoque es más eficiente que generar todos los primos hasta la raíz cuadrada del número. Puedes adaptar este pseudocódigo según el lenguaje de programación que estés utilizando.
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar