ilość liczb pierwszych w przedziale [a, b]

Question

Witam, pomoże ktoś w takim zadaniu?

Na wejściu otrzymuje dwie liczby a oraz b (2 <= a < b <= 10^8). Mam znaleźć ilość liczb pierwszych w tym przedziale. Sposób ze zwykłym przejściem petlą i sprawdzanie liczba po liczbie czy jest pierwsza jest za wolne. Z drugiej strony, sito Eratostenesa nie daje rady ze względu na pamięć. Jest jakiś sensowny pomysł na to zadanie?

Comments

Dlaczego uważasz, że sito jest złe. Liczby masz do 10^8 (czyli 100mln), jeśli użyjesz sita do wygenerowania liczb pierwszych do pierwiatka z tej liczby tj 10^4 (10 tys) to obliczysz te liczby w moment (ułamek sekundy). Czyli sprawdzaj normalnie czy jest pierwsza, ale mając już tabelę liczb pierwszych do 10.000. Ważne pytanie jest takie - czy program ma sprawdzić jeden przedział czy więcej? Jeśli więcej to raz wygenerowane liczby pierwsze możesz wykorzystywać wielokrotnie.

---

@polandonion, Jeszcze spradz tu:
https://en.wikipedia.org/wiki/Prime_gap

Answer 1

Pomiędzy 2 a 10^8 jest tylko 664579 liczb pierwszych. Może da się to jakoś ładnie stablibować?

Albo załatwić co przedziałami - np. podzielić ten przedział na obszary po 10tys. (albo po 1000), i to stablicować. Po tym zostaje Ci tylko kwestia końcówek (tj. od "a" do najbliższej granicy przedziału i od ostatniej granicy do "b"), które możesz bardzo szybko przeszukać normalnie.

Comments

podzieliłem na obszary po 10tyś i wypluwa mi, że kod jest za długi... może zrobić po 100tyś albo po 1mln?

Answer 2

Sita Eratostenesa daje radę, ale z pewnymi optymalizacjami.
Kroki:

1. Utwórz wektor booli o rozmiarze (n+1) i zainicjalizuj go wartościami true. Ten wektor będzie służył do oznaczania liczb jako pierwszych lub niepierwszych.

2. Oznacz liczby 0 i 1 jako niepierwsze, ustawiając odpowiednie wartości w wektorze booli na false.

3. Przejdź przez liczby od 2 do pierwiastka kwadratowego z b (oznaczmy go jako sqrt_b). Dla każdej liczby i sprawdź, czy jest pierwsza (wartość w wektorze booli jest true). Jeśli tak, oznacz wszystkie jej wielokrotności jako niepierwsze (ustaw wartości w wektorze booli dla tych wielokrotności na false). Skacz o i kolejnych liczbach, aby uniknąć powtarzających się wielokrotności.

4. Przejdź przez liczby od a do b. Dla każdej liczby j, jeśli wartość w wektorze booli dla tej liczby jest true, zwiększ licznik liczb pierwszych.

5. Zwróć licznik liczb pierwszych.
   
   
   
    

   int countPrimes(int a, int b)
   {
       std::vector<bool> isPrime(b + 1, true);
       isPrime[0] = false;
       isPrime[1] = false;
   
       int sqrt_b = std::sqrt(b);
   
       for (int i = 2; i <= sqrt_b; i++) {
           if (isPrime[i]) {
               for (int j = i * i; j <= b; j += i) {
                   isPrime[j] = false;
               }
           }
       }
   
       int count = 0;
       for (int i = a; i <= b; i++) {
           if (isPrime[i]) {
               count++;
           }
       }
   
       return count;
   }

    

Comments

Polecę ciekawe stronki przy okazji

https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html

https://medium.com/@thanhdonguyen01/how-to-optimize-sieve-of-eratosthenes-cb5ac681ae77

Answer 3

Ja widzę kilka opcji, pierwsza to właśnie wspomniane tablicowanie, tylko pytanie jaki limit kodu źródłowego, a jak nie to możesz napisać sito, tylko trzymać na vectorze booli i wtedy masz małą pamięć bardzo (taką jak bitset o ile się nie mylę). Sito tak zaimplementowane na pamięci bitsetowej musi wejść.

Comments

limit pamieci to 32 MB

---

No to sito na bitsecie będzie miało niecałe 10MB pamięci o ile dobrze liczę.

---

Tylko o ile wiem, to żeby to miało pamięć bitsetowa, to musisz zrobić mniej więcej coś takiego:

const int size = x;
vector<bool> sito;
sito.assign(size,false);

To jest dziwne, ja nie rozumiem czemu to akurat traktuje jako bitset, ale miałem problem podobny w innym zadaniu i tak właśnie rozwiązałem go. Spróbuj może zadziała. 

---

Ale raczej solv to jest odpowiedź wyzej. Tablicujesz przedziały długości K i tylko znajdujesz prefix i sufix siłowo np. do sqrt. To K faktycznie pewnie może być z 20000 nawet