daily pastebin goal
0%
SHARE
TWEET

Untitled

a guest Nov 16th, 2018 47 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top