java – How can you speed up the algorithm for finding all prime numbers?

Question:

I use the sieve of Eratosthenes algorithm. The search in the range from 2 to 10000 takes 280 ms. I need to find all prime numbers in the range from 2 to the maximum value of an int variable. Use multi-threaded programming? Optimize the algorithm?

import java.util.LinkedList;
import java.util.concurrent.LinkedBlockingDeque;

public class Primes {
private long timeout = System.nanoTime();
LinkedList<Integer> lprimes = new LinkedList<Integer>();
LinkedList<Integer> lnums = new LinkedList<Integer>();
public long getTimeout() {
    return timeout;
}

public void setTimeout(long timeout) {
    this.timeout = timeout;
}

public int getCountPrimes(){
    return this.lprimes.size();
}
public void timeRun() {
    System.out.println(System.nanoTime());
    System.out.println(timeout);
    System.out.println("Время выполнения равно " + String.valueOf(System.nanoTime() - this.timeout)+" ns или " + String.valueOf((System.nanoTime() - this.timeout)/1000000));
}

public void keepPrimes() {
    lnums.add(2);
    for(int i = 3;i <= 10000;i += 2){
           lnums.add(i);
    }
    /*for (int i = 2; i <= 10000; i++) {
        lnums.add(i);
    }*/
    while(lnums.size()>0){
        int nextPrime = lnums.remove();
        for (int i = nextPrime*nextPrime; i <=10000; i+=nextPrime) {
            lnums.removeFirstOccurrence(i);
        }
        lprimes.add(nextPrime);
        System.out.println(nextPrime);
    }
}

public static void main(String[] args) {
    // TODO Auto-generated method stub
    System.out.println("Максимальное значение INT: "+Integer.MAX_VALUE);
    Primes primes = new Primes();
    primes.keepPrimes();
    System.out.println("Формирование коллекции закончено!");
    primes.timeRun();
    System.out.println(primes.getCountPrimes());
}

}

Answer:

Alas, I'm not strong in Java, except to read someone else's code. But…

Yes, there is an algorithm for the sieve of Eratosthenes O(n) , but here the gain compared to a good implementation – O(n lg lg n) – is very small.

But to optimize your code is not something that you can – you need to! For some reason, you collect all odd numbers in a linked list, and then check and remove them from it. What for? Just loop through all the odd numbers in the list. And go not to the last number (10000), but to the square root! It's enough. Look, any composite number greater than the root must have a divisor less than the root – which means it will already be crossed out. All checks for numbers from 100 to 10000 are simply not needed…

And also a very big minus – you use a linked list with constant dynamic memory allocation, indirect calls, long access to elements, etc. – which also prevents the use of the data cache – the solution, as for me, is not good. If it were C++, I would use a compact vector<bool> , having reserved the required amount of memory in advance.

PS I sketched it in C ++ – on my homework it calculated up to 10000 in 16 ms, up to 100000000 – in 557 ms (without displaying it on the screen).