Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

FR_02_13 - Liczby (nie)pierwsze

 

Liczby pierwsze to takie liczby naturalne, które są większe od 1 i mają dokładnie dwa dzielniki (dzielą się tylko przez jeden i przez samą siebie). Pojęcie to nie jest trudne i uczy się o o tym już w szkole podstawowej, jednakże największe umysły matematyczne nie uporały sobie ze znalezieniem wzoru na te liczby. Takie sławy jak Pierre de Fermat, Martin Mersenne, Leonhard Euler czy Johann Carl Friedrich Gauss zmagali się z tymi liczbami tworząc często błędne Hipotezy. Na szczęście twoje zadanie nie będzie aż tak skomplikowane. Dziś zajmiemy się liczbami naturalnymi, które nie są pierwsze. Napisz program, który określi ile jest kolejnych liczb naturalnych w danym przedziale, które nie są pierwsze.

Liczby pierwsze to takie liczby naturalne, które są większe od 1 i mają dokładnie dwa dzielniki (dzielą się tylko przez jeden i przez samą siebie). Pojęcie to nie jest trudne i uczy się o o tym już w szkole podstawowej, jednakże największe umysły matematyczne nie uporały sobie ze znalezieniem ogólnego wzoru na nie. Takie sławy jak Pierre de Fermat, Martin Mersenne, Leonhard Euler czy Johann Carl Friedrich Gauss zmagali się z tymi wspaniałymi liczbami tworząc często błędne Hipotezy. Na szczęście twoje zadanie nie będzie aż tak skomplikowane. Dziś zajmiemy się liczbami naturalnymi, które nie są pierwsze. Napisz program, który określi, jaki jest maksymalny podzbiór kolejnych liczb naturalnych należących do przedziału obustronnie domkniętego, które nie są pierwsze.

 

Wejście

W pierwszym wierszu jedna liczba n określająca ilość zestawów danych (0 < ≤105). Każdy zestaw składa się z dwóch liczb a, b reprezentujących przedział [a, b], gdzie 0 ≤ a ≤ b  4⋅106.

Wyjście

Dla każdego zestawu znajdź największy spójny podciąg kolejnych liczb naturalnych, które nie są pierwsze

Przykład

Wejście:
3
1 10
10 10000
20 22

Wyjście:
3
35
3

Dodane przez:Marcin Kasprowicz
Data dodania:2014-09-13
Limit czasu wykonania programu:0.5s-1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU

ukryj komentarze
2017-07-19 19:32:11 Karol Kurek
" jednakże największe umysły matematyczne nie uporały sobie ze znalezieniem ogólnego wzoru na nie"
Istnieją wzory na liczby pierwsze. Nie istnieje żaden użyteczny (z punktu widzenia złożoności) wzór wyznaczający n-tą liczbę pierwszą, ale to co innego:
http://www.matematyka.wroc.pl/ciekawieomatematyce2/czy-istnieje-wzor-na-n-ta-liczbe-pierwsza
2016-10-06 09:57:36 Miros³aw Falkiewicz
Czy ktoś mógłby sprawdzić czy poprawnie działają procedury testowe do tego zadania?
Aktualnie w historii zgłoszeń nie ma żadnego zaakaceptowanego.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.