Input
The input begins with the number t of test cases in a single line (t<=10). In each of the next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space.
Output
For every test case print all prime numbers p such that m <= p <= n, one number per line, test cases separated by an empty line.
Example
Input:
2
1 10
3 5
Output:
2
3
5
7
3
5
https://www.spoj.pl/problems/PRIME1/
import java.io.*; import java.util.Arrays; public class PrimeGenerator { static final int limite1 = 31700; static final int limite2 = 179; static boolean[] noEsPrimo; public static void main( String args[] ) throws Exception { // Todos los numeros se inicializan como No primos ( false ) noEsPrimo = new boolean[ limite1 ]; // Algoritmo de la criba de Erastostenes, para calcular todos los // numeros primos menores e igual que 31700 for( int i = 2; i <= limite2; i ++ ) { if( !noEsPrimo[ i ] ) { for( int j = i * i; j < limite1; j = j + i ) noEsPrimo[ j ] = true; } } BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) ); int numCasos = Integer.parseInt( br.readLine() ); int a, b; String num[]; for( int i = 0; i < numCasos; i ++ ) { num = br.readLine().split( " " ); a = Integer.parseInt( num[ 0 ] ); b = Integer.parseInt( num[ 1 ] ); mostrarPrimos( a, b ); if( i < numCasos - 1 ) System.out.print( "\n"); } } public static void mostrarPrimos( int a, int b ) { int limite = (int)Math.sqrt( b ); int sigNoPrimo; int longIntervalo = b - a + 1; // False indica que es Primo boolean[] noEsPrimoIntervalo = new boolean[ longIntervalo ]; if( a == 1 ) noEsPrimoIntervalo[ 0 ] = true; for( int i = 2; i <= limite; i ++ ) { if( noEsPrimoIntervalo[ i ] ) continue; // Encontramos el primer multiplo del numero primo i // tal que: a <= i <= b if( a % i == 0 ) sigNoPrimo = a; else sigNoPrimo = i * ( a / i ) + i; // Marcamos los multiplos de i dentro del intervalo [ a, b ] // como numeros no primos for( int j = sigNoPrimo - a; j < longIntervalo; j = j + i ) noEsPrimoIntervalo[ j ] = true; // Puede darse el caso de que el primer multiplo de i dentro del // intervalo [ a, b ] sea un numero primo, este caso se da por // ejemplo cuando a < i if( sigNoPrimo < noEsPrimoIntervalo.length && !noEsPrimoIntervalo[ sigNoPrimo ] ) noEsPrimoIntervalo[ sigNoPrimo - a ] = false; } // Secuencia de caracteres que se mostrara en la salida char[] salida = new char[ ( b - a ) * 5 ]; // Tamanio de la salida ( cantidad de caracteres ) int tamanio = 0; String numero; int longitud; for( int i = a; i <= b; i ++ ) { if( !noEsPrimoIntervalo[ i - a ] ) { numero = i + "\n"; longitud = numero.length(); // Si se sobrepasa el limite del vector, entonces lo copiamos // en uno mas grande if( tamanio + longitud >= salida.length ) salida = Arrays.copyOf( salida, salida.length + 1000 ); // Anadimos la cadena al vector de salida numero.getChars( 0, longitud, salida, tamanio ); tamanio = tamanio + longitud; } } // Mostramos los numeros primos del intervalo [ a, b ] System.out.print( new String( salida, 0, tamanio ) ); } }
#include
ResponderEliminarusing namespace std;
int main(){
int N,M,T;
cin>>T;
for(int n=0; n> M >> N;
int i,j;
for (i = M; i <= N; i++){
j = 2;
while (j <= i && i % j != 0){
j++;
}
if (i == j)
cout << j << endl;
}
cout << endl;
}
return 0;
};
help "time limit exceeded "
DAlvarado_UCLA@hotmail.com
#include
Eliminarusing namespace std;
int main(){
int N,M,T;
cin>>T;
for(int n=0; n> M >> N;
int i,j;
for (i = M; i <= N; i++){
j = 2;
while (j <= i && i % j != 0){
j++;
}
if (i == j)
cout << j << endl;
}
cout << endl;
}
return 0;
};
#include
ResponderEliminarusing namespace std;
int main(){
int N,M,T;
cin>>T;
for(int n=0; n> M >> N;
int i,j;
for (i = M; i <= N; i++){
j = 2;
while (j <= i && i % j != 0){
j++;
}
if (i == j)
cout << j << endl;
}
cout << endl;
}
return 0;
};