Is Using a List instead of an Array for generating Prime Numbers more efficient?

Question

Based on one of the examples,below is a prime number generator for a given cutoff.

My question is in some implementations ,an array is used to mark all the numbers which are multiples until only primes are left.The below is similar in that way but in the below example we need not maintain all the numbers in the array and check if the elements below it are crossed or not during the prime test and only which are not crossed are used in the division.

So is the below better where in we just maintain the primes in a list and which reduces the number of comparisons ?

class PrimesBySieve
{
    public static void main(String args[]){
        generateTo(20);
    }

    public static void generateTo(int cutoff) 
    {
        try {
            ArrayList<Integer> primes = new ArrayList<Integer>();
            primes.add(2);


            int j;
            boolean isPrime;
            for(int i=3;i<=cutoff;i++){

                //Check if i is Prime by dividing with all the primes in the list which       
                //are smaller than i
                //Any number can be expressed as a product of primes
                j=0;
                isPrime=true;
                while(primes.get(j)*primes.get(j)<=i && j<=primes.size()){
                    if(i%primes.get(j)==0){
                        isPrime=false;
                    }
                    j++;
                }

                //Add the prime to the output.
                if(isPrime){
                    primes.add(i);
                }
            }   
            System.out.println(primes);
        }
        catch(Exception e){
            System.out.println(e.getMessage());
        }
    }

}

Answer 1

Your algorithm is not efficient. So regardless of which data structure you use
you won't get a great performance speed-up. You should use another algorithm
called 'Sieve of Eratosthenes'. Try to implement this algorithm and you'll notice
the difference in performance (especially for bigger values of N). Currently you
have N=20.

Sieve of Eratosthenes