Números Primos de nuevo

Points: 100 (partial)

Time limit: 3.0s

Java 8 6.0s

Python 6.0s

Memory limit: 64M

Author:

jabetancourt

Problem type

Allowed languages

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

Los competidores están exahustos de problemas sobre números primos. Pero ellos realmente saben que los entrenadores son malvados y que van a querer incluir otro problema de esta área. Dado un número entero $X$ ~X~, los participantes deben encontrar el intervalo más corto $[A, B]$ ~[A, B]~ que contiene a $X$ ~X~. ¡Esperen un segundo! ¿Qué hacen? Este no es un problema de números primos, de hecho este es más simple que $A+B$ ~A+B~. Claro que $A$ ~A~ y $B$ ~B~ deben ser... usted sabe.

Entrada

La primera línea de entrada contiene un entero $M (1 \leq M \leq 100)$ ~M (1 \leq M \leq 100)~. Continuan $M$ ~M~ líneas, cada una con un número $X (1 < X \leq 10^5)$ ~X (1 < X \leq 10^5)~

Salida

$M$ ~M~ líneas conteniendo $A$ ~A~ y $B$ ~B~ $(1 < A \leq B \leq 10^6)$ ~(1 < A \leq B \leq 10^6)~, $B-A \leq 10^4$ ~B-A \leq 10^4~.

Ejemplo de entrada

2
2
4

Ejemplo de salida

2 2
3 5

Comments

0

Anthony08 commented on Dec. 9, 2023, 3:02 p.m.

Me da RTE segmentation fault el ultimo caso ._.

0

Ãńõńÿmøūš commented on March 21, 2023, 6:47 p.m.

LO hice con fuerza bruta

0

Alejandro777 commented on Feb. 18, 2020, 7:40 p.m.

me da rte

6

aniervs commented on Feb. 19, 2020, 4:08 p.m.

En efecto, estás accediendo a la posición 100000 de un arreglo de tamaño 100000. Aumenta en 1 el tamaño del arreglo.

3

josed commented on Feb. 18, 2020, 7:44 p.m.

Chequea que no estés accediendo a un índice fuera de rango en un arreglo

0

luisalfredo commented on Feb. 5, 2020, 3:02 p.m.

Alguien me puede ayudar aquí

2

aniervs commented on Feb. 19, 2020, 5:48 p.m.

Otra idea puede ser precalcular A y B. O sea: si $l_i$ ~l_i~ es el mayor primo menor o igual que $i$ ~i~ y $r_i$ ~r_i~ es el menor primo mayor o igual que $i$ ~i~, entonces si $i$ ~i~ es primo, $l_i=r_i=i$ ~l_i=r_i=i~ y si no, $l_i=l_{i-1} \text{ y } r_i=r_{i+1}$ ~l_i=l_{i-1} \text{ y } r_i=r_{i+1}~. Entonces cada pregunta la puedes responder en tiempo constante.

3

aniervs commented on Feb. 19, 2020, 5:37 p.m. ← edited →

Este problema se puede hacer con Fuerza bruta porque son pocas preguntas, si fueran $10^5$ ~10^5~ preguntas: Mira, tienes que buscar para cada $x$ ~x~ que te preguntan, el mayor número primo menor o igual que $x$ ~x~ y el menor número primo mayor o igual que $x$ ~x~. Primero con la criba de Erathostenes sacas todos los primos y los guardas ordenados en un arreglo. Ahora cada vez que pregunten por un $x$ ~x~, con búsqueda binaria puedes encontrar los dos valores q necesitas. Puedes hacer la búsqueda binaria con la STL, B es el lower_bound, y A es la posición anterior al upper_bound.