Liczba półpierwsza


Liczba półpierwsza w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do wyszukiwania

Liczba półpierwsza – liczba naturalna będąca iloczynem dokładnie dwóch, niekoniecznie różnych liczb pierwszych.

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.

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, 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 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 = 3 11 , 34 = 2 17 , 35 = 5 7 {\displaystyle 33=3\cdot 11,\quad 34=2\cdot 17,\quad 35=5\cdot 7}
  • 85 = 5 17 , 86 = 2 43 , 87 = 3 29 {\displaystyle 85=5\cdot 17,\quad 86=2\cdot 43,\quad 87=3\cdot 29}
  • 93 = 3 31 , 94 = 2 47 , 95 = 5 19 {\displaystyle 93=3\cdot 31,\quad 94=2\cdot 47,\quad 95=5\cdot 19}

Interesującym przypadkiem jest liczba 216 = ( 2 3 ) 3 , {\displaystyle 216=(2\cdot 3)^{3},} z której obu stron znajdują się trójki liczb półpierwszych.

Na podstawie artykułu: "Liczba półpierwsza" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy