Guest User

Untitled

a guest
Nov 16th, 2018
170
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.ArrayList;
  2.  
  3. public class Main {
  4. static int N = 10000;
  5. static int[] sieve;
  6. static ArrayList<Integer> primes;
  7. public static void main(String args[]) {
  8. long start = System.nanoTime();
  9. fillSieve();
  10. long end = System.nanoTime();
  11. System.out.println("OLD : " + primes.size() + " , time : " + (end-start)/1000000.0);
  12.  
  13. start = System.nanoTime();
  14. fillSieve2();
  15. end = System.nanoTime();
  16. System.out.println("NEW : " + primes.size() + " , time : " + (end-start)/1000000.0);
  17.  
  18. }
  19.  
  20. static void fillSieve(){
  21. sieve = new int[N];
  22. primes = new ArrayList<Integer>();
  23. for(int i = 2; i < N; ++i){
  24. if(sieve[i] == 0){
  25. primes.add(i);
  26. for(int j = i*i; j < N; j += i){
  27. sieve[j] = 1;
  28. }
  29. }
  30. }
  31. }
  32.  
  33. static void fillSieve2(){
  34. sieve = new int[N];
  35. primes = new ArrayList<Integer>();
  36. for(int i = 2; i < N; ++i){
  37. if(sieve[i] == 0)
  38. primes.add(i);
  39. for(int j=0, si=primes.size(); j<si && i*primes.get(j)<N ; j++)
  40. {
  41. sieve[primes.get(j)*i] = 1;
  42. if(i%primes.get(j)==0) break;
  43. }
  44. }
  45. }
  46. }
RAW Paste Data