Liczba półpierwsza

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Liczba półpierwsza – liczba rozkładająca się na iloczyn dokładnie dwóch liczb pierwszych (na dokładnie dwa czynniki pierwsze).

Liczby półpierwsze odgrywają znaczącą rolę w kryptografii, bowiem liczba czynników pierwszych ma bezpośredni związek ze złożonością obliczeniową faktoryzacji.

Interesującą własnością takich liczb jest następujące stwierdzenie:

liczby półpierwsze występują maksymalnie po trzy obok siebie.

Wynika to z podzielności przez 4. Nie może być 4 kolejnych liczb półpierwszych, bo jedna z nich byłaby podzielna przez 4, a więc podzielna przez 2 i przez dwa, zatem musiałaby być równa 4. Ale 4 nie należy do żadnej czwórki kolejnych liczb półpierwszych, bo 3 i 5 nie są półpierwsze.

Przykłady[edytuj | edytuj kod]

Oto trójki kolejnych liczb półpierwszych mniejszych niż 1000:

  • (33,34,35)
  • (85,86,87)
  • (93,94,95)
  • (121,122,123)
  • (141,142,143)
  • (201,202,203)
  • (213,214,215)
  • (217,218,219)
  • (301,302,303)
  • (393,394,395)
  • (445,446,447)
  • (633,634,635)
  • (697,698,699)
  • (841,842,843)
  • (921,922,923)

Przykładowe faktoryzacje:

  • 33=3x11 34=2x17 35=5x7
  • 85=5x17 86=2x43 87=3x29
  • 93=3x31 94=2x47 95=5x19

Interesującą ciekawostką jest liczba 216 = (2·3)3, z której obu stron znajdują się trójki liczb półpierwszych.