# 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;

public class Primes {
private long timeout = System.nanoTime();
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() {
for(int i = 3;i <= 10000;i += 2){
}
/*for (int i = 2; i <= 10000; i++) {
}*/
while(lnums.size()>0){
int nextPrime = lnums.remove();
for (int i = nextPrime*nextPrime; i <=10000; i+=nextPrime) {
lnums.removeFirstOccurrence(i);
}
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());
}
``````

}

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.
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.