- 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;
}
}
Sunday, May 15, 2011
Prime Generator v2- runs in CodeChef
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment