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 ).