Sunday, May 15, 2011

Prime Generator v2- runs in CodeChef


  1. This one passes through CodeChef's judge in 8.36 seconds, still 2.36 seconds slower than it should.

    import java.util.*;import java.io.*;
    public class Main {
    /** * @param args the command line arguments */ static LinkedHashSet<Integer> primes = new LinkedHashSet<Integer>();

    public static void main(String[] args) throws Exception{ //for(int i = 2; i<100000; i++) // if(isPrime(i)) // primes.add(i);

    BufferedReader k = new BufferedReader(new InputStreamReader(System.in));
    int m = Integer.parseInt(k.readLine());
    for(int i =1; i<=m; i++){ if(i!=1) System.out.println("\n");
    StringTokenizer st = new StringTokenizer(k.readLine());
    int a = Integer.parseInt(st.nextToken());
    int b = Integer.parseInt(st.nextToken());
    boolean first = true;
    for(int j = a; j<=b; j++ ){ if(isPrime(j)){ primes.add(j);
    if(first){ first=false;
    System.out.print(j);
    } else System.out.print("\n"+j);
    } } }
    } static boolean isPrime(int n){ if(n<2) return false;


    double d = Math.sqrt(n);

    for(Integer p: primes){ if(p>d) break;
    if(n%p==0)
    return false;
    } return true;
    }
    }

No comments:

Post a Comment