Zadanie z liczbami pierwszymi

Ekhem.. nie działa obrazek to dam treść

Haker Adam zaczął ostatnio analizować pewną metodę szyfrowania. Szybko zauważył, że szyfrowanie odbywa
się z wykorzystaniem szczególnych liczb. Są to liczby pierwsze oraz iloczyny dwóch liczb pierwszych (niekoniecznie
różnych).

Wejście:
W pierwszym wierszu standardowego wejścia znajduje się jedna liczba naturalna n (1 <= n <= 100 000), oznaczająca
liczbę zestawów danych. Każdy zestaw składa się z dwóch liczb naturalnych a i b (0 <= a <= b <= 1 000 000),
będących początkiem i końcem przedziału domkniętego [a, b].
W testach wartych łącznie około 40% punktów zachodzą dodatkowe warunki n <= 5 000, b <= 10 000.

Wyjście:
Twój program powinien wypisać na standardowe wyjście n wierszy – po jednym dla każdego zestawu danych.
W wierszu o numerze i powinna znajdować się dokładnie jedna liczba całkowita, oznaczająca ile jest liczb
wykorzystywanych do szyfrowania, należących do przedziału określonego w i-tym zestawie danych.

Czy w tym zadaniu trzeba wykorzystać jakieś dodatkowe właściwości liczb pierwszych? Bo z tego co patrzyłem to przy tylu zestawach danych i wielkościach przedziałów to limit czasu będzie przekroczony przy szukaniu z użyciem for'a (a trzeba jeszcze znaleźć iloczyny ).

nie widać obrazka, popraw

https://pl.wikipedia.org/wiki/Test_Millera-Rabina

Przy czym liczby pierwsze nie większe niż 1000 wpisz twardo do kodu (nie jest ich dużo).

To możesz spróbować to rozwiązać w taki sposób :

1. Robisz preprocessing znajdując wszystkie liczby pierwsze na przedziale [1,1000000] korzystając z algorytmu Sito Erastotenesa w czasie O(N log N ) gdzie N ~ 10^6

2. Dostaniesz M liczb pierwszych, gdzie M < 80 000.

3. Robisz nowa tablice bool exist[] gdzie exist[i] oznacza ze da sie wygenerowac liczbe i biorac iloczyn dwoch liczb pierwszych lub gdy i jest liczba pierwsza

4. Robisz 2 fory lecac po wszystkich liczbach pierwszych i oznaczajac exist[M[i]] = true oraz exist[M[i]*M[j]] = true . Zajmie to O(M^2)

5. Robisz nowa tablice count[] gdzie count[i] to ile liczb ma exist ustawione na true na przedziale [0..i] . Zajmie to O(N) gdzie N~10^6

6. Na kazde zapytanie o przedzial a,b mozesz teraz odpowiadac w czasie O(1) zwracajac wynik (count[b] - count[a-1])

Przy danych limitach powinno przejść takie rozwiazanie

Spróbuje zrobić za jakiś czas i pewnie dam znać :s

#include <iostream>
#include <stdio.h>
using namespace std;

long long il,a,b,ilp; bool tab[1000001]={0};

int main()
{
    cin>>il;
    tab[1]=1; tab[0]=1;
    for(long long j=2;j*j<=1000001;++j){
            if(tab[j]==0)
                for(long long k=j*j;k<=1000001;k+=j)
                    tab[k]=1;
    }
    for(long long i=0;i<il;++i){
        scanf("%lld",&a); scanf("%lld",&b);
        ilp=0;
        for(long long j=a;j<=b;++j){
            if(tab[j]==0){
                for(long long k=j;k<=b;++k){
                    if(tab[k]==0&&j*k>=a&&j*k<=b&&tab[k*j]==1)ilp++;
                }
            }
        }
        for(long long j=a;j<=b;++j)if(tab[j]==0)ilp++;
        cout<<ilp<<endl;
    }
}
 

Mam takie coś, ale jest niezbyt czytelne i tylko 20 pktów. Na 10 testów 2ok / 2błędne / reszta limit

błąd w generowaniu sita. Przekopuj kod z wiki.

Nie pakuj wszystkiego do main, definiuj funkcje klasy itp!

Program przy dużych liczbach pada na tym fragmencie

for(long long j=a;j<=b;++j){
            if(tab[j]==0){
                for(long long k=j;k<=b;++k){
                    cout<<"TEST2"<<endl;
                    if(tab[k]==0&&j*k<a&&j*k>b&&tab[k*j]==1)ilp++;
                }
                cout<<"TEST3"<<endl;
            } 

Postaram się chyba napisać całość jeszcze raz...

tu masz działające sito:
http://ideone.com/ktPWqG

Wziąłem sito z wikipedii i pozmieniałem tak, że ostateczny kod wygląda:

 #include <iostream>
using namespace std;

bool tab[1000001]; int il,tabP[90000],ilp=0,w,tabilP[1000001]={0},sm=0,x,y;

int main()
{
     tab[0]=true; tab[1]=true;
     for (int i=2; i*i<=1000000; i++)
    {
        if(tab[i] == false){
             tabP[ilp]=i; ilp++;
        }
        if (tab[i] == true)
            continue;
        for (int j = 2*i ; j <=1000000; j += i)
            tab[j] = true;
    }

    for(int i=0; i<ilp; i++){
        for(int j=i;j<ilp;++j){
            w=tabP[i]*tabP[j];
            if(w<1000001)tab[w]=0;
        }
    }
    for(int i=0; i<=1000000 ; i++){
        if(tab[i]==false)sm++;
        tabilP[i]+=sm;
    }

    cin>>il;
    for(int i=0; i<il; i++){
        cin>>x>>y;
        cout<<tabilP[y]-tabilP[x-1]<<endl;
    }
}

Tym razem 30pkt ehh... Sprawdzałem pojedyncze mniejsze zakresy i zgadzało się z odpowiedzami ( może coś z tymi większymi jest źle? ). Mogę poprosić o analizę kodu?

1. Ściągnij najpierw tablice danych do vector<pair<unsigned,unsigned>>, przy okazji licz max.
2. Sito rób do max+1.
3. Wywal wszystkie tablice oprócz jednej, ta jedna ma być typu unsigned (nie bool).
4. Pamiętaj w jednej zmiennej ilość poprzednich liczb pierwszych (przed pętlą od 2 jest ich 0).

Wektorów jeszcze nie miałem :(

To zrób zwykłą tablicę na tyle ile może być tych par.