martes, 31 de mayo de 2011

Prime Generator

Peter wants to generate some prime numbers for his cryptosystem. Help him! Your task is to generate all prime numbers between two given numbers!
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 ) );
   }
}

3 comentarios:

  1. #include
    using 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

    ResponderEliminar
    Respuestas
    1. #include
      using 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;
      };

      Eliminar
  2. #include
    using 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;
    };

    ResponderEliminar