Подсчет простых чисел в заданном интервале


Так, вот это Hackerearth вопрос, относительно (более или менее) подсчет количества простых чисел между заданной парой чисел (до 106).

Потом были 3 основных вариантов, доступных для меня:

  1. Метод пробного деления, и его вариантов.
  2. Решето Эратосфена
  3. Сегментного решета Эратосфена.

Как узнал из этого ответа.

Наивный испытание методом разделения, и его вариантов выдал "превышено ограничение по времени" ошибки около 70 % тестов.

Оба решета Эратосфена и его сегментированное версия дал "превышение лимита времени" ошибка на 60 % теста.

Вот мой код :

import java.util.* ;
import java.io.BufferedReader ;
import java.io.InputStreamReader ;
/*
Trial division : failed. 6 points
Sieve of Eratosthenes : failed 8 points.
Segmented sieve of Eratosthenes : failed.  8 points.
*/
public class MoguLovesNumbers
{
    public static void main(String args[]) throws Exception
    {
        BufferedReader bro = new BufferedReader(new InputStreamReader(System.in)) ;
        int T = Integer.parseInt(bro.readLine()) ;
        for(int t=0;t<T;t++)
        {
            String[] S = bro.readLine().split(" ") ;
            int l = Integer.parseInt(S[0]) ;
            int r = Integer.parseInt(S[1]) ;
            int temp = l<r?l:r ;
            r = l<r?r:l ;
            l = temp ;


            System.out.println(segmentedSieve(l,r)) ;
        }


    }
    static void sieveOfEratosthenes(int l,int r,List<Integer> prime)
    {
        boolean[] mark = new boolean[r+1] ;
        int counter = 0 ;
        Arrays.fill(mark,true ) ;

        for(int i=2;i<r+1;i++)
        {
            if(mark[i])
            {
                if(i>=l)
                {
                    prime.add(i) ;
                    counter++ ;
                }
                for(int j=i*2;i*i<=r && j<r+1;j+=i)
                    mark[j] = false ;
            }
        }
        // return counter ;
    }
    static int segmentedSieve(int l,int n)
    {
        int limit = (int)Math.sqrt(n)+1 ;
        List<Integer> prime = new ArrayList<Integer>() ;
        sieveOfEratosthenes(0,limit,prime) ;
        int low = limit ;
        int high = limit*2 ;
        int count = 0 ;
        while(low<n)
        {
            if(high>n)
                high = n ;
            boolean mark[] = new boolean[limit+1] ;
            Arrays.fill(mark,true ) ;
            for(int i=0;i<prime.size();i++)
            {
                int loLim = (int)(Math.ceil((float)low/prime.get(i)))*prime.get(i) ;
                for(int j=loLim;j<=high;j+=prime.get(i))
                {
                    mark[j-low] = false ;
                }
            }
            for(int i = 0;i<mark.length;i++)
                if(mark[i] && (i+low>=l)&& (i+low<=high))
                {
                    count++ ;
                }
            low+=limit ;
            high+=limit ;
        }
        if(l<=Math.sqrt(n)+1)
        {
            for(int i=0;i<prime.size();i++)
                if(prime.get(i)>=l)
                    count++ ;
        }
        return count ;

    }
}

Материалы:


Вопрос:

Как этот код более эффективным? Сегментированное сито и простой решето, как работать в O(N log(log(N))) время.



Комментарии
1 ответ

Переосмыслив

Очевидное изменение, которое бросается сразу же на меня, чтобы сделать свой список простых чисел в объект или даже поле класса. Тогда вам не придется воссоздавать свои праймы каждый раз. Вы могли бы создать его в первый раз. Позже ты просто продлить его. Поле объекта будет лучше практикой программирования, но поле класса будет работать для этой проблемы.

Вы даже можете прочитать в ВСЕ ввести, а затем создать список простых чисел для всех из них. Или просто построить его до миллиона перед обработкой входных данных. Конечно, это было ошибкой, если у них есть некоторые тесты, где проезжают значит, не рассчитав всех миллионов. Учитывая ваш текущий алгоритм, будет достаточно легко вычислить все простые числа от 0 до 1000 заранее.

Рассмотреть вопрос о проведении штрихов в NavigableSet. Потому что то, что вы хотите знать, сколько простых чисел в диапазоне. Так что можно заменить

            System.out.println(segmentedSieve(l,r)) ;

с

            System.out.println(primes.subSet(l, r).size());

Для подсчета простых чисел в наборе [l, r) если primes это NavigableSet проведение не менее всех простых чисел меньше, чем r.

Если вам нужно посчитать [l, r] или (l, r)вы будете использовать длинную версию с логическими значениями для всеохватности.

Конкретные советы


    static void sieveOfEratosthenes(int l,int r,List<Integer> prime)

Вы никогда не называют это с l как угодно, но не 0. Так что вы могли бы также сказать

    static void sieveOfEratosthenes(int r, List<Integer> prime)

Тогда вы можете избавиться от проверки в цикле:


                if(i>=l)

Это всегда верно, если l равна нулю и i по крайней мере 2. Вы не должны проверить его.

Вам не нужно counter переменной. Как это, она равна prime.size() и вы никогда не использовать его. Исключения оно сохраняет операцию. Компилятор может сделать это за вас, но вам не нужно это.


                for(int j=i*2;i*i<=r && j<r+1;j+=i)

Это может быть

                for (int j = i*i; j <= r; j += i)

Вы только должны проверить с i*i. Все, что меньше, что уже будет отмечен. Например, вы уже отмечены все делится на 2, так i*2 будет отмечен для всех i больше или равна 1.

Вы нужны только для проверки i*i<=r один раз. Это все равно, что проверить, как первая итерация j равно i*i.

В j<r+1 и j <= r эквивалентны, если j и r являются целыми числами.

1
ответ дан 16 марта 2018 в 03:03 Источник Поделиться