Strona główna » Algorytmy » Teoria Liczb » Liczby Półpierwsze
2
 

Liczby Półpierwsze

https://mattomatti.com/a74

Definicja

Liczby Półpierwsze to takie liczby naturalne, które są iloczynem dwóch liczb pierwszych niekoniecznie różnych od siebie.

Przykłady

Najmniejsza liczba pierwszą jest 2, dlatego najmniejsza liczba Półpierwsza to . 5 nie będzie liczb półpierwszą, ponieważ jest liczbą pierwszą i jedyny iloczyn to 1 i 5, a 1 nie jest pierwsza. Z kolei liczba 6 już jest.

Pierwsze 10 liczb półpierwszych to: 4, 6, 9, 10, 14, 15, 21, 22, 25, 26, ...

Implementacja

Do rozpoznania liczby półpierwszej potrzebna jest znajomość rozpoznawania liczby pierwszej. Wyjaśnienie rozpoznawania liczb pierwszych znajduje się tutaj. Podczas pisania kodu warto zauważyć, że dla zadanej liczby a trzeba znaleźć jej najmniejszy dzielnik. Jeśli dzielnik nie jest równy liczbie a to trzeba sprawdzić czy iloraz a przez najmniejszy dzielnik jest liczbą pierwszą. Jeśli tak jest to zostało udowodnione, że liczba jest półpierwsza.

Do zrealizowania zadania przydatna będzie funkcja pierwszyDzielnik(), która zwróci pierwszy właściwy dzielnik dla podanej liczby. W przeciwnym wypadku zwrócona zostanie wartość 0. Przez właściwy dzielnik należy rozumieć dzielnik, która jest mniejszy od podanej liczby.

  1. int pierwszyDzielnik(int a){
  2.   for(int i = 2; i <= sqrt(a); i++){
  3.     if(a % i == 0){
  4.       return i;
  5.     }
  6.   }
  7.   return 0;
  8. }

Wyszukiwanie dzielnika w przedstawionym algorytmie jest identyczne ze sprawdzaniem czy icz jest pierwsza. W tym jednak przypadku zamiast zwracać fałsz, że liczba nie jest pierwsza to zostanie zwrócona wartość najmniejszego dzielnika. Można to zrobić w ten sposób, ponieważ najmniejszy dzielnik dowolnej liczby naturalnej, prócz 1, jest liczbą pierwszą.

Posiadając funkcję pierwszyDzielnik()

  1. bool czyPolpierwsza(int a) {
  2.   int dzielnik = pierwszyDzielnik(a);
  3.   return (dzielnik != 0 && pierwszyDzielnik(a / dzielnik) == 0);
  4. }

Testowanie funkcji

Powyższą funkcję czyPolpierwsza() można wykorzystać do wypisania wszystkich liczb półpierwszych z zakresu od 1 do 100:

  1. int main () {
  2.   for(int i = 1; i < 100; i++){
  3.     if(czyPolpierwsza(i))
  4.     cout << i << endl;
  5.   }
  6.   system("pause");
  7.   return 0;
  8. }
Zadania

Liczby półpierwsze występują maksymalnie po 3 koło siebie co jest uzależnione od dzielnika 4. Przykładowa pierwsza taka trójka to (33, 34, 35).

Zadanie 1

Napisz program, który wczyta od użytkownika zakres [a, b], a następnie wypisze wszystkie trójki liczb półpierwszych. Każda trójka liczb powinna się znaleźć w oddzielnej linijce. Na koniec program powinien wypisać ile znalazł trójek w podanym zakresie.

Przykładowo dla danych:

  1. 1 100

otrzymamy:

  1. 33 34 35
  2. 85 86 87
  3. 93 94 95