Как можно ускорить алгоритм нахождения всех простых чисел?

#java #алгоритм #простые_числа

Использую алгоритм решето Эратосфена.
Поиск в диапазоне от 2 до 10000 выполняется 280 мс.
Мне нужно найти все простые числа в диапазоне от 2 до максимального значения переменной INT.
Использовать многопоточное программирование? Оптимизировать алгоритм?

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

public class Primes {
private long timeout = System.nanoTime();
LinkedList lprimes = new LinkedList();
LinkedList lnums = new LinkedList();
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());
}


}
    

Ответы

Ответ 1

Увы, я в Java не силен, разве что читать чужой код. Но...

Да, есть алгоритм решета Эратосфена O(n), но тут выигрыш по сравнению с хорошей реализацией
- O(n lg lg n) - очень небольшой. 

А вот оптимизировать ваш код не то что можно - нужно! 
Вы зачем-то собираете все нечетные числа в связанный список, а потом проверяете и
убираете их из него. Зачем? Просто проходите по всем нечетным числам в списке. И проходите
не до последнего числа (10000), а до квадратного корня! Этого достаточно. Смотрите,
любое составное число, большее корня, должно иметь делитель, меньше корня - а значит,
оно уже будет вычеркнуто. Все проверки для чисел от 100 и до 10000 просто не нужны...

И еще тоже очень большой минус - вы используете связанный список с постоянным динамическим
выделением памяти, косвенными обращениями, долгим доступом к элементам и т.п. - что
еще и не дает использовать кэш данных - решение, как по мне, нехорошее. Если бы это
был C++, я бы использовал компактный vector, заранее зарезервировав необходимое
количество памяти.

P.S. На C++ набросал - на моей домашней просчитало до 10000 за 16 мкс, до 100000000
- за 557 мс (без вывода на экран).


Ответ 2

Вывод простых чисел от 2 до 2**31-1 на C

#include 
#include 
#include 
#define lim INT32_MAX
#define BITS 32
int main()
{
    uint32_t *x= calloc(sizeof*x, ((unsigned)lim-3+BITS*2-1)/(BITS*2));
    fputs("2\n", stdout);
    for(unsigned i=3;i<=lim;i+=2) {
        unsigned b= i-3 >> 1;
        if(x[b/BITS] & 1<>1) ) x[b/BITS] |= 1<
#include 
#include 
#define lim INT32_MAX
#define BITS 32
int main()
{
    uint32_t *x= calloc(sizeof*x, ((unsigned)lim-5+BITS*3-3)/(BITS*3));
    fputs("2\n3\n", stdout);
    for(unsigned i=5, b0=0; i<=lim; i+=6, b0++) {
        unsigned b=b0;
        if(!( x[b/(BITS/2)] & 1<
Ответ 3

Заинтересовал ответ sercxjo. Поигрался немного. На моей машине его код, скомпилированный
VC++ 2015, работает (без вывода) 12 с. Там же мой вариант

#include 
#include 
#include 

constexpr inline unsigned long pow2(unsigned long i) { return 1 << i; }

unsigned long isqrt(unsigned long a)
{
    unsigned long x = a;
    for(unsigned long z = 0; x != z; )
    {
        z = x;
        x = (x + a/x)/2;
    }
    return x;
}

constexpr unsigned long MAX_LIM = pow2(31) - 1;
constexpr unsigned long ARR_LIM = (MAX_LIM >> 6) + 1;
const     unsigned long SQR_LIM = isqrt(MAX_LIM);;

unsigned long primes[ARR_LIM] = { 0 }; // 0 - простое, 1 - составное

auto set_primes = [](unsigned long idx)
    { primes[idx >> 6] |= pow2((idx&0x0000003F)>>1); };
auto get_primes = [](unsigned long idx)
    { return primes[idx >> 6] &  pow2((idx&0x0000003F)>>1); };

int main(int argc, const char * argv[])
{
    for(unsigned long i = 3; i <= SQR_LIM; i += 2)
    {
        if (get_primes(i)) continue;
        for(unsigned long j = i * i; j <= MAX_LIM; j += 2*i)
        {
            set_primes(j);
        }
    }

    puts("2");
    for(unsigned long i = 3; i <= MAX_LIM; i+=2)
    {
        if (get_primes(i)) continue;
        printf("%lu\n",i);
    }
}


считает (опять же, без вывода) 7.82 с. Результаты совпадает :)

Интересно, что если перебирать простые вида , то намечается даже проигрыш по времени...

Лямбды использовал сознательно - компилятор их очень хорошо оптимизирует.

Следующим номером должно быть просеивание через решето Эратосфена с использованием
шаблонов во время компиляции :) Кто готов взяться?