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<Long> invalidated = new ArrayList<>(); // where invalidated numbers will be stored.
// prepare
double maxFac = Math.sqrt(max);
int f = 2;
while(f <= 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<Long> primes = new ArrayList<>();
long i = 3; // current test
for(long l : invalidated){
primes.add(l);
}
while(i <= 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() >= 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.