Skocz do zawartości
Roundstic

Funkcja Eulera

Rekomendowane odpowiedzi

Mam problem z napisaniem jednej własności funkcji załączonej na obrazku.

Napisałem takie coś:


void rozklad(int n) 
{
   int k;
   k=2;
   int fi;
   fi = 1;

   while(n>1)
   {
       while(n%k==0)
       {
           n = n/k;
           fi= fi*funkcja1(k);
       }
       k++;
   }
   cout<<fi;

}

 

Ale problem jest taki, że to liczy fi(2)*fi(2)*fi(3) = 1*1*2=2, a powinno liczyć fi(4)*fi(3)=2*2=4 i nie wiem jak zrobić żeby to zliczało potęgi.

post-613872-15773911655803_thumb.jpg

Edytowane przez Roundstic

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

A nie możesz zaczynać od "k=n-1" i potem "k--" zamiast "k++" plus dodatkowy warunek w zewnętrznym while, żeby k nie spadło poniżej tego 2? I chyba powinno pomijać sytuację gdy n=k*k a jeszcze lepiej zawsze sprawdzać czy "gcd(n/k, k) = 1", wtedy nie będzie nawet potrzeby zmieniania kierunku, po prostu pomijasz te dzielenie, dla którego nie wychodzą względnie pierwsze czynniki.

Edytowane przez litestep

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

A nie możesz zaczynać od "k=n-1" i potem "k--" zamiast "k++" plus dodatkowy warunek w zewnętrznym while, żeby k nie spadło poniżej tego 2?

No nie bardzo, bo ten wzór opiera się na założeniu, że znajdujesz rozkład na liczby pierwsze. Idąc od góry dostaniesz najpierw złożone dzielniki jeżeli istnieją.

 

I chyba powinno pomijać sytuację gdy n=k*k

Zakładam, że robi to tajemnicza funkcja1, choć fakt, że ten algorytm jakiś dziwny jest.

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

Jeśli chcesz dodać odpowiedź, zaloguj się lub zarejestruj nowe konto

Jedynie zarejestrowani użytkownicy mogą komentować zawartość tej strony.

Zarejestruj nowe konto

Załóż nowe konto. To bardzo proste!

Zarejestruj się

Zaloguj się

Posiadasz już konto? Zaloguj się poniżej.

Zaloguj się

  • Ostatnio przeglądający   0 użytkowników

    Brak zarejestrowanych użytkowników przeglądających tę stronę.

×
×
  • Dodaj nową pozycję...