Decyzja, czy interwał zawiera liczbę pierwszą

Jaka jest złożoność decyzji, czy przedział liczb naturalnych zawiera liczbę pierwszą? Wariant Sita Eratostenesa daje algorytm , w którym jest długością przedziału, a ukrywa czynniki polilarytmiczne w punkcie początkowym przedziału; czy możemy zrobić lepiej (pod względem samego )?L∼$\tilde O(L)$$L$$\sim$$L$

Zastrzeżenie : Nie jestem ekspertem w teorii liczb.

Krótka odpowiedź : jeśli jesteś gotów do przyjęcia „rozsądnych liczbowo teoretyczne przypuszczenia”, to możemy powiedzieć, czy jest najlepszym w przedziale w czasie . Jeśli nie jesteś skłonny przyjąć takiego założenia, istnieje piękny algorytm dzięki Odlyzko, który osiąga , i uważam, że jest to najlepiej znany.$[n, n+\Delta]$$\mathrm{polylog}(n)$$n^{1/2 + o(1)}$

Bardzo pomocny link z dużą ilością świetnych informacji o ściśle powiązanym problemie : projekt PolyMath dotyczący deterministycznych algorytmów wyszukiwania liczb pierwszych .

Długa odpowiedź :

Jest to trudny problem, aktywny obszar badań i wydaje się być ściśle związany z trudną kwestią ograniczania luk między liczbami pierwszymi. Twój problem jest moralnie bardzo podobny do problemu znalezienia liczby pierwszej między a deterministycznie, który był ostatnio przedmiotem projektu PolyMath . (Jeśli chcesz naprawdę zagłębić się w te pytania, ten link jest doskonałym miejscem do rozpoczęcia.) W szczególności nasze najlepsze algorytmy dla obu problemów są zasadniczo takie same.2 $n$$2n$

W obu przypadkach najlepszy algorytm zależy w dużej mierze od wielkości przerw między liczbą pierwszą. W szczególności, jeśli jest takie, że zawsze istnieje liczba pierwsza między n i n + f ( n ) (i f ( n ) można obliczyć efektywnie), to zawsze możemy znaleźć liczbę pierwszą w czasie p o l y l o g ( n ) ⋅ f ( n ) w następujący sposób. Aby ustalić, czy istnieje liczba pierwsza między n i n $f(n)$$n$$n + f(n)$$f(n)$$\mathrm{polylog}(n) \cdot f(n)$$n$ , najpierw sprawdź, czy Δ ≥ f ( n ) . Jeśli tak, wyślij tak. W przeciwnym razie po prostu iteruj przez liczby całkowite między n i n + Δ i przetestuj każdą z nich pod kątem pierwszeństwa i odpowiedz tak, jeśli znajdziesz liczbę pierwszą, a nie inaczej. (Można to zrobić deterministycznie, dlatego deterministyczne znalezienie liczby pierwszej między n a 2 n jest tak ściśle związane z ustaleniem, czy liczba pierwsza występuje w określonym przedziale.)$n + \Delta$$\Delta \geq f(n)$$n$$n + \Delta$$n$$2n$

$\mathrm{polylog}(n)$$f(n) = O(\log^2 n)$$n \geq 3$$1/\log n$

$f(n) \leq O(\sqrt{n})$$f(n) \leq O(\sqrt{n} \log n)$$n^{o(1)}$

$\widetilde{O}(n^{0.525})$$n^{0.025}$