Улучшение производительности ситового метода

Я пишу метод поиска простых чисел до n (решето Эратосфена), да, это домашнее задание. Я хочу улучшить производительность в методе, который я написал. Я настраивал это в течение последних нескольких дней, но не могу следовать указанному псевдокоду и повышать производительность.

псевдокод выглядит следующим образом:
создайте очередь чисел для обработки
заполните очередь целыми числами от 2 до n включительно
создайте пустую очередь результатов для хранения простых чисел
повторите следующие шаги:
получить следующее простое число p, удалив первое значение из очереди чисел
поместить p в результирующую очередь простых чисел
выполнить цикл по очереди чисел, удаляя все числа, делящиеся на p
while(p меньше квадратный корень из n)
все остальные значения простые, поэтому перенесите их в очередь простых результатов

вот мой текущий метод:

 public static Queue<Integer> getPrimes(int n) throws IllegalArgumentException
{
    if (n<2)
    {
        throw new IllegalArgumentException();
    }

    Queue<Integer> integers = new LinkedList<Integer>();
    Queue<Integer> primes = new LinkedList<Integer>();
    for (int i = 2; i <= n ; i++) {
        integers.add(i);
    }
    boolean[] isMultiple = new boolean[n + 1];

    for(int iterate = integers.remove(); iterate <= n; iterate++)
    {

        if(!isMultiple[iterate])
        {
            primes.add(iterate);
            for(int multiples = iterate * iterate; multiples >= 0 && multiples <= n; multiples += iterate)
            {
                isMultiple[multiples] = true;
            }
        }
    }
    return primes;
}

java queue sieve
person D4RKCIDE    schedule 25.02.2015    source источник

Ответы (2)


arrow_upward
3
arrow_downward

Сначала вы можете оптимизировать его двумя способами: 1) Вам не требуется integer связанный список. Вместо этого используйте простой цикл for.

2) После того, как вы используете цикл for, вы можете сначала удалить все четные числа, поскольку они, очевидно, делятся на 2. А затем просто пройти через нечетные числа. Таким образом убавляем петлю до половины.

Фрагмент кода:

    primes.add(2);
    for(int i=2;i*i<=n;i++)
    {
        isMultiple[2*i]=true;
    }
    for(int i=3;i*i<=n;i+=2)
    {
        if(!isMultiple[i]) 
        {
            primes.add(i);
            for(int j=i*i;j<n;j+=i)
            {
               isMultiple[j]=true;
            }
        }
    }
    return primes;
person Rahul Shah    schedule 25.02.2015
comment
Отличная идея, включая 2 сразу и повторяя только нечетные числа. - person D4RKCIDE; 25.02.2015

arrow_upward
0
arrow_downward

В качестве первого небольшого шага вы можете удалить очередь integers и заменить ее обычным циклом for:

for (int iterate = 2; iterate < n; iterate++)
{
     if (!isMultiple[iterate]) 
     {
         ...
     }
}
person Uli    schedule 25.02.2015
comment
Да, к сожалению, это один из шагов, которым я должен следовать. Первоначально я написал метод, который даже не содержал очереди целых чисел. позвольте мне добавить псевдокод к исходному вопросу, это моя вина, извините. - person D4RKCIDE; 25.02.2015