Prawidłowa definicja totientu

Borneq · Post autor: **Borneq** » 30 wrz 2016, o 15:08

Była

funkcja ...przypisująca każdej liczbie naturalnej liczbę liczb względnie z nią pierwszych nie większych od niej samej

zmieniona na

funkcja ... przypisująca każdej liczbie naturalnej liczbę liczb względnie z nią pierwszych mniejszych od niej samej.

Dla n pierwszej mamy \(\displaystyle{ \varphi(n) = n-1}\), np. dla n=5 będzie to 4. Z jednej strony 1 nie jest liczbą pierwszą, ale czy 1 może być nazwane wględnie pierwszą choć nie jest pierwsza? Poprawiona definicja była by prawidłowa, ale znowu w

Kod: Zaznacz cały

https://oeis.org/A000010

podają

Euler totient function phi(n): count numbers <= n and prime to n

Jak się oblicza tę funkcję? należy rozłożyć n na czynniki czy jest szybszy sposób?

dec1 · Post autor: **dec1** » 30 wrz 2016, o 15:29

1) Mniejszych.

2) \(\displaystyle{ 1}\) jest oczywiście względnie pierwsza z każdą liczbą całkowitą, liczby względnie pierwsze nie muszą być pierwsze.

3) Niestety trzeba rozłożyć liczbę na czynniki.

Kod: Zaznacz cały

https://gist.github.com/cslarsen/1635288

jest niezła implementacja w C++

Borneq · Post autor: **Borneq** » 30 wrz 2016, o 18:15

A gdzie znaleźć funkcję binary_gcd?

dec1 · Post autor: **dec1** » 30 wrz 2016, o 18:18

Jest napisane w komentarzu na górze, że trzeba sobie napisać funkcję sprawdzającą pierwszość, obliczającą NWD (binary nawiązuje do

Kod: Zaznacz cały

https://en.wikipedia.org/wiki/Binary_GCD_algorithm

algorytmu, szybszego niż algorytm Euklidesa) i wygenerować vector liczb pierwszych.

Do C++17 została dodana funkcja gcd, lecz można ją też otrzymać w C++14 przez std::__gcd(x).