search

marceloarenassaavedra / IIC2283-2-21

19 stars 2 forks source link

[Tarea 3] Pregunta 1 Cantidad de primos y límite de tiempo #56

Open VicenteMerino opened 2 years ago

VicenteMerino commented 2 years ago

Hola, quería preguntar si es que podemos asumir que para rangos altos hay un número considerable de primos. Por ejemplo para

a = 48145541333841014311012455010560827071655059028340200497424 b = 48145541333841014311012455010560827071655059028340200501400

Hay un solo primo p = 48145541333841014311012455010560827071655059028340200501399

Por lo que encontrarlo puede variar mucho, llegando en el peor de los casos a 5 segs.

Además quiero preguntar si es que el tiempo de 2 segundos se respetará para todos los test cases con que prueben la tarea?

N9199 commented 2 years ago

No pueden asumir que el "prime gap" es "pequeño" para los rangos de la tarea, pero pueden ver si encuentran formas de optimizar el algoritmo para que logra correr en menos de 2s. En caso de que aún con optimizaciones existan casos donde la solución oficial no pasa en 2s se considerará subir un poco el tiempo.

VicenteMerino commented 2 years ago

Se puede saber, con ese input que puse en cuanto se demora la oficial en pasar en promedio?

VicenteMerino commented 2 years ago

Podríamos por ejemplo jugar con la probabilidad de error para bajar el tiempo? O es requisito la probabilidad 1/2**100?