Prime number generation algorithm I'm making a prime number scanning algorithm in Java. It uses the concept of the Sieve of Eratosthenes to efficiently find the prime numbers.

It works well and can calculate all the prime numbers under 1,000,000 in less than a second on my laptop, but I was wondering how the algorithm could be further improved.

public static void eratoImproved(long max){

    long start = System.currentTimeMillis();

    ArrayList&lt;Long&gt; invalidated = new ArrayList&lt;&gt;(); // where invalidated numbers will be stored.

    // prepare
    double maxFac = Math.sqrt(max);
    int f = 2;
    while(f &lt;= maxFac){
        boolean isNew = true;
        for(long l : invalidated){
            if(f % l == 0){
                isNew = false;
            }
        }
        if(isNew) {
            invalidated.add(Math.round(f + 0.0));
        }
        f++;
    }

    ArrayList&lt;Long&gt; primes = new ArrayList&lt;&gt;();

    long i = 3; // current test

    for(long l : invalidated){
        primes.add(l);
    }

    while(i &lt;= max){
        boolean v = true;
        for(long s : invalidated){
            if(i % s == 0){
                v = false;
                break;
            }
        }

        if(v){
            primes.add(i);
            long m = 2*i;
            if(primes.size() &gt;= 150){
                String s = Math.round(((i + 0.0)/max)*100) + "%: ";
                for(long l : primes){
                    s += l + "/";
                }
                System.out.println(s);
                primes.clear();
            }

        }
        i += 2;
    }
    System.out.println("Completed search!");
    String s = "Remaining primes: ";
    for(long l : primes){
        s += l + "/";
    }
    System.out.println(s);
    primes.clear();

    System.out.println("Conducted search in " + (System.currentTimeMillis() - start)/1000 + " seconds.");
}


I've optimized everything I can think of, but I wanted to get a second opinion.
Answer by janos is good, but is more about style. Here are some functional/performance observations related to your stated goal of efficiency.


invalidated.add(Math.round(f + 0.0)), huh???
f coerced to double, add a zero, call round(). Why?
Suggest change f from int to long, and just use invalidated.add(f).
while(f &lt;= maxFac){ is done by continually coercing f to double and comparing the double values. Change maxFac to long using cast (truncation is ok here, no need for rounding).
for(long l : invalidated){ primes.add(l); } is a long way of saying primes.addAll(invalidated), except you're adding the overhead of unboxing and reboxing the values.
You have two identical loops of invalidated to determine if prime. Move to reusable method (DRY).
Never do String += String in a loop. Use a StringBuilder.
And again, what's with the i + 0.0?

StringBuilder buf = new StringBuilder();
buf.append(Math.round(i * 100.0 / max)).append("%: ");
for (Long prime : primes)
    buf.append(prime).append('/');
System.out.println(buf);