¿Cuántos primos?

Points: 100 (partial)

Time limit: 10.0s

Memory limit: 64M

Java 128M

Authors:

Forte11, ralcolea, reinier, tomaso

Problem type

Allowed languages

Ada, Assembly, Awk, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Perl, Prolog, Python, Scala, Swift, VB

En varias ocasiones, se le darán dos enteros $A$ ~A~ y $B$ ~B~ ( $1 \leq A \leq B \leq 5*10^7$ ~1 \leq A \leq B \leq 5*10^7~), imprima la cantidad de números primos en el rango $[A, B]$ ~[A, B]~.

Entrada

$(0 < T < 10^6)$ ~(0 < T < 10^6)~, el número de casos de prueba.

Luego seguirán $T$ ~T~ líneas, cada una conteniendo dos enteros $A$ ~A~ y $B$ ~B~, descritos arriba.

Salida

Para cada línea, excepto la primera, deberá imprimir, en una sola línea, la cantidad de números primos en el rango dado, siguiendo el siguiente formato: Test Case #: (donde el símbolo # deberá ser sustituido por el número del caso de prueba correspondiente y deberá ser cambiado por la cantidad requerida de número primos).

Ejemplo de entrada

Ejemplo de salida

Test Case #1: 2
Test Case #2: 1
Test Case #3: 1

Comments

0

angelmh commented on Dec. 2, 2023, 2:44 a.m.

Para Java creo que el límite de memoria a 64MB es algo corto

1

josed commented on Dec. 3, 2023, 5:01 p.m.

Aumenté la memoria de Java para que una solución que entra en C++ entre también en Java. Los envíos han sido rejuzgados :)

1

angelmh commented on Sept. 17, 2023, 11:47 p.m.

Alguien que me ayude con la fórmula, la que uso no me da, (n/ln(n))

3

karellgz commented on Sept. 18, 2023, 12:37 a.m.

Me temo que no hay fórmula, esa que usas es una aproximación de la cantidad de primos hasta $n$ ~n~ que es bastante exacta para un $n$ ~n~ grande.

(Alerta de spoiler de la solución)

Lo que podrías hacer es precomputarlos, y luego mediante una estructura de datos o por búsqueda respondes las consultas.

1

angelmh commented on Sept. 18, 2023, 2:35 a.m. ← edited →

Ahí está la trampa de este ejercicio creo. Son números tan grande como 5e7, o sea, no cabe almacenar ni en array ni el list. Eso es simplemente lo que complica todo a pesar de que no te permite almacenar 5e7 valores ya que simplemente se va de memoria la respuesta

3

linkyless commented on Sept. 18, 2023, 3:51 a.m.

Recomiendo investigar sobre el bitset. Es una estructura de datos bastante eficiente para almacenar conjuntos de bits, cada bit puede estar encendido o apagado, y de esa forma te lo puedes tomar como si fuera un arreglo de booleanos tradicional para el tema de identificar números primos, solo que, en el caso del array de booleanos, este utiliza un byte (8 bits) para representar un valor. Un bitset utiliza mucha menos memoria que eso, ya que cada bit solo ocupa 1 bit de memoria. Luego, quizás con búsqueda binaria, puedas acceder a los valores que buscas luego de precomputar los primos.

0

angelmh commented on Sept. 18, 2023, 5:09 p.m.

cierto, el bitset es una estructura muy eficiente en todos los sentidos pero aun así creo que el costo de computar todos los primos es muy alto, usando un bitset y una criba adaptada me da TLE en las pruebas 3 y 4

8

linkyless commented on Sept. 19, 2023, 4:44 a.m.

Para evitar el TLE el último paso consiste en dividir el intervalo A y B. En este caso lo que tienes que hacer es calcular la cantidad de primos en cada segmento de forma individual. Me explico, podrías dividir el rango en segmentos de longitud constante, como $[a, a + K], [a + K + 1, a + 2K], [a + 2K + 1, a + 3K]$ , y así, donde K es un value que puedes ajustar según tus necesidades. Esto, llevado a este problema y más simplificado, consiste en guardar los números primos como tal en un arreglo aparte (la cantidad de primos de 1 a 5e7 caben en un arreglo tradicional, aunque para evitar problemas, puedes intentar pushearlos en un vector). Cuando tengas la cantidad de primos en cada segmento, podrías sumarlos para obtener la cantidad total de primos en el rango [A, B]. Es algo así como una suma en prefijos, pero para ello, debes adaptar tu código para utilizar búsqueda binaria y así sacar las posiciones que te hacen falta.

Si quieres más pistas, puedes utilizar la STL, ahí existen dos funciones importantes que aplican búsqueda binaria para encontrar el primer y el último número primo en cada segmento que esté dentro del rango de la consulta (en este caso, solo utilizaríamos el rango de números primos y no el bitset, el bitset solo era una herramienta importante para la Criba de Eratóstenes).

Las funciones son el lower_bound y el upper_bound, que, en esencia, lo único que hacen es encontrarte la posición del primer número que es mayor o igual que el valor dado, y el upper_bound te devuelve la posición al primer elemento que es mayor que el valor dado (realmente te devuelve un iterador, pero con restarle el iterador al array, te devolvería la posición y no el iterador).

La diferencia entre estos dos iteradores (o posiciones) te da el número de elementos entre ellos, casi como una suma en prefijos.

La complejidad temporal pasaría a ser $O(n(log(log(n))) + t(log n))$ ~O(n(log(log(n))) + t(log n))~, siendo n el limite del intervalo y t la cantidad de casos.

0

legion06 commented on Jan. 21, 2023, 2:16 a.m.

es porque declaras el arreglo con un tamaño 5e7+10 y el array solo llega a un poco mas de 1e6

1

Leroy commented on Jan. 20, 2023, 10:09 p.m.

alguien me podria decir la razón por la que me da RTE mi código?

1

legion06 commented on July 10, 2022, 4:26 p.m.

alguien me puede decir porque mi programa da rte segmention fault

1

josed commented on July 11, 2022, 12:21 p.m.

La constante MAX que declaraste es menor que el máximo valor que pueden tomar $A$ ~A~ y $B$ ~B~