Generador de primos

Publicado en 'Programación' por Alguno, 14 May 2013.





  1. Alguno

    Alguno Miembro frecuente

    Registro:
    30 Ago 2009
    Mensajes:
    140
    Likes:
    10




    Hola gente , estaba resolviendo un problema de spoj sobre un generador de primos(lo estoy haciendo en C) y me marca wrong answer si alguien puede ayudarme aquí esta mi código
    Código:
    #include<stdio.h>
    #include<math.h>
    int primo(i){int aux,j;if(i==1)return 0 ;else if(i==2 || i==3)return 1;else for(j=2;j<=sqrt(i);j++){aux=i%j;
                  if(aux==0)return 0;}return 1;}//verifico si es primo
    int main(){
    long long int j,i,t,vector[20];
    scanf("%lld",&t);
    for(j=0;j<=(t*2)-1;j=j+2){scanf("%lld %lld",&vector[j],&vector[j+1]);}//entrada de intervalos
    for(j=0;j<=(t*2)-1;j=j+2){
    if(vector[j]>=1 && vector[j+1]>=vector[j] && vector[j+1]<=1000000000 && vector[j]*vector[j+1]<=100000)
    {for(i=vector[j];i<=vector[j+1];i++)//recorro el intervalo
    {if(primo(i))printf("%lld\n",i);}}printf("\n");}
    return 0;}
    El problema original es este
    Código:
    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
    Fuente:http://www.spoj.com/problems/PRIME1/ :hi:
     
    A tomy! le gustó este mensaje.


  2. tenguman

    tenguman Miembro de plata

    Registro:
    15 Nov 2010
    Mensajes:
    3,142
    Likes:
    1,016
    en el for de J estas incluyendo un numero double o decimal en donde obligatoriamente tiene que ir un numero entero, antes de empezar el for sacas la raiz de i y luego la transformas a entero redondeando hacia arriba
     
  3. Alguno

    Alguno Miembro frecuente

    Registro:
    30 Ago 2009
    Mensajes:
    140
    Likes:
    10
    Si igualara la raiz a una variable auxiliar entera solo para sacar su parte entera y de ahi comparar creo seria la forma de solucionar eso , umm me olvide mencionar que el programa compila y saca los primo solo que de la pregunta daba me sale wrong answer (en la pagina que menciono como fuente ), lo que no se es que si el programa tiene algún error o es que estoy entendiendo mal la pregunta :(