Generator liczb pierwszych

Generator liczb pierwszych wypisuje wszystkie liczby pierwsze z podanego przedziału, np. od 1 do 100 albo od miliona do miliona tysiąca. Przydaje się przy zadaniach z matematyki, do sprawdzenia własnych obliczeń, a programistom do przygotowania danych testowych.

Oprócz listy generator pokazuje, ile liczb pierwszych jest w zakresie, jaką część zakresu stanowią, ile wśród nich jest par bliźniaczych i jaka jest największa przerwa między kolejnymi liczbami pierwszymi. Jeśli chcesz sprawdzić jedną konkretną liczbę, skorzystaj z kalkulatora liczb pierwszych.

1. Wpisz początek i koniec zakresu albo wybierz gotowy zakres, np. „do 1000”.
2. Kliknij Znajdź liczby pierwsze albo naciśnij Enter w jednym z pól.
3. Przy zakresie do 1000 liczb zobaczysz sito. Przełącznik Lista pokazuje same liczby pierwsze.
4. Skopiuj wynik albo pobierz go jako TXT lub CSV.

Jeden zakres może obejmować do miliona kolejnych liczb, a jego koniec może sięgać biliona. Gdy wpiszesz granice w odwrotnej kolejności albo przekroczysz limit, generator poprawi zakres i napisze, co zmienił.

Liczba pierwsza to liczba naturalna większa od 1, która dzieli się bez reszty tylko przez 1 i przez samą siebie. Pierwsze z nich to 2, 3, 5, 7, 11 i 13. Liczba 2 jest jedyną parzystą liczbą pierwszą, bo każda inna liczba parzysta dzieli się przez 2.

Liczby większe od 1, które mają jeszcze inne dzielniki, to liczby złożone, np. 12, które dzieli się przez 2, 3, 4 i 6. Jedynka nie należy do żadnej z tych grup.

Każdą liczbę naturalną większą od 1 można zapisać jako iloczyn liczb pierwszych i to tylko na jeden sposób, jeśli pominąć kolejność czynników, np. 60 = 2 × 2 × 3 × 5. To zasadnicze twierdzenie arytmetyki. Jego istotną część znał już Euklides, a pełny dowód jednoznaczności rozkładu podał Carl Friedrich Gauss w 1801 roku.

Generator korzysta z metody, którą przypisuje się greckiemu uczonemu Eratostenesowi z Cyreny, żyjącemu w III wieku p.n.e. Zamiast sprawdzać każdą liczbę osobno, sito wykreśla liczby złożone z całej listy naraz:

1. Wypisz liczby od 2 do górnej granicy.
2. Weź pierwszą niewykreśloną liczbę, czyli 2, i wykreśl jej wielokrotności: 4, 6, 8 i dalej.
3. Przejdź do następnej niewykreślonej liczby, czyli 3, i wykreśl 9, 15, 21 i dalej. Mniejsze wielokrotności, jak 6 i 12, są już wykreślone.
4. Powtarzaj, aż dojdziesz do pierwiastka z górnej granicy. Liczby, które zostały, są pierwsze.

Wystarczy dojść do pierwiastka, bo każda liczba złożona ma dzielnik nie większy od swojego pierwiastka. Dla zakresu do 100 trzeba więc wykreślić tylko wielokrotności 2, 3, 5 i 7. Widok sita w generatorze pokazuje ten efekt: po najechaniu na przekreśloną liczbę widać jej rozkład z najmniejszym dzielnikiem.

Dla zakresów daleko od zera, np. od biliona, generator liczy sito odcinkami. Najpierw znajduje liczby pierwsze do pierwiastka z górnej granicy, czyli do miliona, a potem wykreśla ich wielokrotności tylko w wybranym fragmencie. Dzięki temu nie musi przechowywać wszystkich liczb od 1 do biliona.

Nieskończenie wiele. Dowód podał Euklides: gdyby liczb pierwszych było skończenie wiele, ich iloczyn powiększony o 1 nie dzieliłby się przez żadną z nich, więc musiałaby istnieć jeszcze jedna liczba pierwsza.

Im dalej, tym rzadziej się pojawiają. Twierdzenie o liczbach pierwszych mówi, że wśród liczb do x jest ich w przybliżeniu x/ln x. Przybliżenie zaniża wynik, ale względny błąd maleje wraz ze wzrostem x:

Mimo rozrzedzenia wciąż zdarzają się liczby pierwsze bliźniacze, czyli pary różniące się o 2, np. 11 i 13 albo 1 000 037 i 1 000 039. Nie wiadomo, czy jest ich nieskończenie wiele. W 2013 roku Yitang Zhang udowodnił, że nieskończenie wiele par liczb pierwszych różni się o mniej niż 70 milionów, a rok później zespół projektu Polymath zmniejszył tę granicę do 246.

Do 200 jest 46 liczb pierwszych: 25 w pierwszej setce i 21 w drugiej.

1. 2
2. 3
3. 5
4. 7
5. 11
6. 13
7. 17
8. 19
9. 23
10. 29
11. 31
12. 37
13. 41
14. 43
15. 47
16. 53
17. 59
18. 61
19. 67
20. 71
21. 73
22. 79
23. 83
24. 89
25. 97
26. 101
27. 103
28. 107
29. 109
30. 113
31. 127
32. 131
33. 137
34. 139
35. 149
36. 151
37. 157
38. 163
39. 167
40. 173
41. 179
42. 181
43. 191
44. 193
45. 197
46. 199

Rozkład jest nieregularny. Między 100 a 110 są cztery liczby pierwsze (101, 103, 107 i 109), a między 114 a 126 nie ma żadnej, bo 113 i 127 dzieli przerwa 14.

• Liczba 2^{136 279 841} − 1, odkryta w październiku 2024 roku w projekcie GIMPS, ma 41 024 320 cyfr. Gdy ją odkryto, była największą znaną liczbą pierwszą.
• Liczby postaci 2^p − 1 to liczby Mersenne'a. Żeby taka liczba była pierwsza, wykładnik p musi być pierwszy, ale to nie wystarcza: 2¹¹ − 1 = 2047 = 23 × 89.
• Spiralę z hero opisał polski matematyk Stanisław Ulam w 1963 roku. Ukośne linie odpowiadają wielomianom kwadratowym, które dają liczby pierwsze częściej niż przeciętnie.
• Hipoteza Riemanna z 1859 roku dotyczy rozkładu liczb pierwszych. Należy do Problemów Milenijnych, za których rozwiązanie Instytut Claya wyznaczył nagrodę miliona dolarów.
• Niektóre cykady w Ameryce Północnej wychodzą z ziemi co 13 albo 17 lat. Jedna z hipotez mówi, że okres będący liczbą pierwszą utrudnia zgranie się z cyklami drapieżników.

Więcej o historii metod szukania liczb pierwszych przeczytasz w artykule o ewolucji metod generowania liczb pierwszych.