Strona główna » Algorytmy » Teoria Liczb » Liczby Sfeniczne
 

Liczby Sfeniczne

https://mattomatti.com/a39

Liczba sfeniczna

Liczba doskonała jest liczbą naturalną, która jest iloczynem trzech różnych liczb pierwszych. Innymi słowy jest postaci: n = a·b·c, gdzie n to liczba sfeniczna, a, b, c to liczby pierwsze. Liczba takiej postaci będzie miała wtedy dokładnie 8 dzielników: {1, a, b, c, ab, bc, ac, n}.

Pierwsze pięć liczb sfenicznych to: 30, 42, 66, 70, 78, ...

Przykłady

Przykładowo weźmy liczbę 30, 30 = 2·3·5, więc jest liczbą sfeniczną. Innym przykładem jest 66, która rozkłada się następująco 66 = 2·3·11.

Implementacja

Funkcja pomocnicza

Podczas kodowania pomocna będzie funkcja, która powie czy liczba jest pierwsza. Szerzej na temat szukanie liczb pierwszych tutaj.

  1. bool prime(int n, int o=2){
  2.   return (o<=sqrt(n)) ? (n%o==0) ? false : prime(n,++o) : true;
  3. }

Największy pierwszy dzielnik

W założeniu funkcja divideByPrime() ma za zadanie znaleźć liczbę i, która będzie pierwsza i dzieląca podaną liczbę a. Po znalezieniu liczby podzieli liczbę a przez i i zwróci i.

  1. int divideByPrime(int &a, int from){
  2.   for(from++;from<=a;from++){
  3.     if(prime(from) && a % from == 0){
  4.       a /= from;
  5.       return from;
  6.     }
  7.   }
  8.   return 0;
  9. }

(2.) Rozpoczynamy poszukiwania liczby i w zakresie [from + 1, a]. (3.) Jeśli kolejna liczba i jest pierwsza i dzieli a to (4.) dzielimy a przez znalezioną liczbę oraz zwracamy znalezioną liczbę i. Jeśli jednak nie znajdziemy liczby pierwszej dzielącej a to (8.) zwracamy 0.

Czy Sfeniczna?

Funkcja isSphenic() przyjmuje jeden argument n, który na koniec zwraca wartość logiczną czy liczba n jest sfeniczna.

  1. bool isSphenic(int n){
  2.   int a, b, c;
  3.   if((a = divideByPrime(n, 1)) == 0)
  4.     return false;
  5.   if((b = divideByPrime(n, a)) == 0)
  6.     return false;
  7.   if((c = divideByPrime(n, b)) == 0)
  8.     return false;
  9.   if(n != 1)
  10.     return false;
  11.   return true;
  12. }

(2.) Deklarujemy zmienne tymczasowe a, b, c. (3.) Szukamy liczby pierwszej, która dzieli n i buforujemy w zmiennej a. Jeśli zmienna a wyniesie 0 to znaczy, że funkcja divideByPrime() nie znalazła dzielącej liczby pierwszej czyli liczba nie może być sfeniczna, dlatego zwracamy wtedy false. Powtarzamy ten schemat jeszcze dwa razy. Jednak za każdym razem wskazując, aby nowa znaleziona liczba pierwsza była większa od poprzedniej zbuforowanej. Na sam koniec (9.) sprawdzamy czy n wynosi 1. Tylko wtedy n = a•b•c. Jeśli nie to (10.) zwracamy false. W przeciwnym wypadku (11.) true.

Dowód czy liczba sfeniczna

Dopiszemy drugą funkcję isSphenicProve(), która nie tylko sprawdzi czy liczba jest sfeniczna, ale również wypisze na ekran rozkład tej liczby. Jest to właściwie funkcja isSphenic() z dodaną linijką przed oryginalną (11.):

  1.   cout << a*b*c << " = " << a << "*" << b << "*" << c << endl;

Pierwsze n liczb sfenicznych

Dopiszemy drugą funkcję isSphenicProve(), która nie tylko sprawdzi czy liczba jest sfeniczna, ale również wypisze na ekran rozkład tej liczby. Jest to właściwie funkcja isSphenic() z dodaną linijką przed oryginalną (11.):

  1. void writenSphenic(int n){
  2.   int i = 2;
  3.   while(n > 0) {
  4.     if(isSphenic(i)){
  5.       cout << i << endl;
  6.       n--;
  7.     }
  8.     i++;
  9.   }
  10. }

(2.) Deklarujemy zmienną i, która będzie nam przechowywać, którą liczbę sprawdzamy pod kątem bycia liczbą sfeniczną. Zaczynamy od 30, ponieważ wiemy, że jest to najmniejsza liczba sfeniczna. (3.) Poszukiwania n liczb sfenicznych będziemy kontynuować aż n osiągnie 0, ponieważ po każdej znalezionej liczbie zmniejszymy n o 1. (4.) Jeśli i-ta liczba jest sfeniczna to (5.) wypisujemy ją na ekran i (6.) zmniejszamy n o 1. Na koniec pętli (8.) zwiększamy i o 1.

Testowanie programu

Poniższa funkcja main() wczyta od użytkownika liczbę n, a potem wypisze czy liczba jest sfeniczna. Następnie na ekran zostanie wypisane pierwsze pięć liczb sfenicznych.

  1. int main () {
  2.   int n;
  3.   cin >> n;
  4.   cout << (isSphenic(n) ? "TAK" : "NIE") << "\n\n";
  5.   cout << "Pierwsze piec liczb sfenicznych:\n";
  6.   writenSphenic(5);
  7.   system("pause");
  8.   return 0;
  9. }

Zadania

Zadanie 1

Napisz funkcję writenSphenicFromTo(), która przyjmie dwa argumenty całkowite from, to, które określą z jakiego zakresu [from, to] liczby sfeniczne mają zostać wypisane.