Poszukiwanie liczb pierwszych

[Troll81]

Chciałbym dla ciekawych rozwinąć nieco temat, ku powszechnemu dobru ogólnemu.

na początek trochę teorii

Liczba pierwsza to liczba naturalna, która ma dokładnie dwa dzielniki naturalne: jedynkę i siebie samą, np.
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, itp.
Liczby naturalne większe od 1, które nie są pierwsze, nazywa się liczbami złożonymi. Z podanych definicji wynika, że liczby 0 i 1 nie są ani pierwsze, ani złożone.

Liczby naturalne mają pewne własności oprócz tego ze nie dzielą się przez nic oprócz 1 i samej siebie.
- Najmniejszy różny od jedynki dzielnik naturalny liczby naturalnej jest liczą pierwszą
- Żaden skończony zbiór nie zawiera wszystkich liczb pierwszych
- Każda liczba naturalna większa od 1 daje się jednoznacznie zapisać w postaci iloczynu skończonego niemalejącego ciągu pewnych liczb pierwszych. Liczby pierwsze są atomami, z których przy pomocy mnożenia zbudowane są pozostałe liczby.

Najprostsza metoda szukania liczb pierwszych jest sito Eratostenesa: jeśli liczba naturalna N większa od 1 nie jest podzielna przez żadną z liczb pierwszych nie większych od pierwiastka z N, to N jest liczbą pierwszą.

Rozmieszczenie liczb pierwszych wśród liczb naturalnych spełnia pewne prawidłowości statystyczne, ale nie jest znany żaden wzór, który pozwalałby wyznaczać liczby pierwsze w sposób bardziej efektywny niż metoda Eratostenesa.

istnieją też szczególne rodzaje liczb pierwszych
Liczby bliźniacze
Liczby pierwsze p i q są bliźniacze jeśli p = q + 2. Przykłady: 3 i 5, 5 i 7, 11 i 13, 17 i 19, 29 i 31, 41 i 43, 59 i 61, 71 i 73...
5 jest bliźniacza zarówno z 3 jak i z 7.
Nie wiadomo, czy istnieje nieskończenie wiele bliźniaczych liczb pierwszych.

Liczby pierwsze czworacze
liczby pierwsze,mające postać p, p+2, p+6, p+8, np. 5, 7, 11 i 13 lub 101, 103, 107 i 109, czyli dwie pary liczb bliźniaczych w najbliższym możliwym sąsiedztwie.

Liczby pierwsze izolowane
Liczba pierwsza p jest izolowana, jeśli najbliższa jej liczba pierwsza różni się od p co najmniej o 4. Przykłady:23, 89, 157, 173.

Liczby lustrzane pierwsze
To pary liczb pierwszych, z których jedna powstaje przez zapisanie cyfr dziesiętnych drugiej w odwrotnej kolejności. Przykłady: 13 i 31, 17 i 71, 37 i 73, 79 i 97, 107 i 701,...

Liczby palindromiczne pierwsze
To liczby pierwsze, które nie zmieniają się, gdy ich cyfry dziesiętne zapiszemy w odwrotnej kolejności. Przykłady: 11, 101, 131, 191, 929.

No dobra ale po co komu liczby pierwsze?
Liczby pierwsze są stosowane w niektórych znanych algorytmach kryptograficznych. Jednym z takich jest RSA.

oczywiście temat jest znacznie szerszy i bardziej złożony. Istnieje wiele hipotez wciąż jeszcze nie udowodnionych i zapewne jeszcze więcej czekających na odkrycie.
Projektem który zajmuje się liczbami pierwszymi w BOINC jest właśnie Primegrid.

[GRID]

Jeden ze starszych wątków na forum - szukanie liczb pierwszych

Oraz opis projektu poszukującego liczb pierwszych i liczb Mersenne'a