Использую алгоритм решето Эратосфена. Поиск в диапазоне от 2 до 10000 выполняется 280 мс. Мне нужно найти все простые числа в диапазоне от 2 до максимального значения переменной INT. Использовать многопоточное программирование? Оптимизировать алгоритм?
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());
}
}