Napiši program koji određuje koliko ima prirodnih brojeva m manjih ili jednakih od datog broja n koji su uzajamno prosti sa n tj. za koje je 1≤m≤n i nzd(m,n)=1.
Sa standardnog ulaza unosi se broj n (1≤n≤2⋅109).
Na standardni izlaz ispisati samo traženi broj.
9
6
Brojevi uzajamno prosti sa brojem n su brojevi 1, 2, 4, 5, 7 i 8 i ima ih ukupno 6.
1
1
Broj 1 zadovoljava uslove 1≤1 i nzd(1,1)=1.
Funkciju φ(n) koja izračunava broj brojeva uzajamno prostih sa n proučavao je Leonard Ojler, pa se ova funkcija obično naziva Ojlerova funkcija.
Naivni pristup izračunavanju zasnivao bi se na brojanju elemenata koji su uzajamno prosti sa datim brojem n (dakle, na brojanju elemenata koji zadovoljavaju dati uslov), pri čemu bismo proveru da li su dva broja uzajamno prosta mogli zasnovati na izračunavanju NZD i primeni Euklidovog algoritma (brojevi su uzajamno prosti ako i samo ako im je NZD jednak 1).
#include <iostream>
using namespace std;
int nzd(int a, int b)
{
while (b > 0) {
int tmp = b;
= a % b;
b = tmp;
a }
return a;
}
int phi(int n)
{
int count = 0;
for (int i = 1; i <= n; i++) {
if (nzd(i, n) == 1) {
++;
count}
}
return count;
}
int main()
{
int n;
>> n;
cin
<< phi(n) << endl;
cout
return 0;
}
Ipak, matematička svojstva Ojlerove funkcije nam daju način da njenu vrednost mnogo brže izračunamo. Evo o kojim svojstvima je reč:
Funkcija φ je multiplikativna, tj. ako su a i b uzajmno prosti brojevi, tada je φ(a⋅b)=φ(a)⋅φ(b). Najlakše je razumeti zašto je to tako kada se brojevi od 1 do a⋅b napišu u a redova po b brojeva. Tada će oni brojevi koji su uzajamno prosti sa a⋅b da se nađu u φ(a) redova po φ(b) brojeva. Ova osobina je značajna jer vrednosti multiplikativnih funkcija mogu veoma efikasno da se izračunaju na osnovu razlaganja argumenta na proste činioce i izračunavanja vrednosti funkcije za proste činioce.
Ako je p prost broj, tada je φ(p)=p−1, jer su svi brojevi koji su manji od p, uzajamno prosti sa p.
Ako je p prost broj, broj brojeva uzajamno prostih sa brojem pk je φ(pk)=pk−pk−1=pk⋅(p−1p). Zaista, od svih pk brojeva iz intervala [1,pk], jedini koji nisu uzajamno prosti sa pk su umnošci broja p, a to su brojevi p, 2p, 3p, …, pk−1⋅p. Njih ima pk−1, što dokazuje tvrđenje.
Dakle, ako se broj n rastavlja kao pk11⋅…⋅pkmm, tada je
φ(n)=φ(pk11)⋅…⋅φ(pkmm)=(pk11⋅(p1−1p1))⋅…⋅(pkmm⋅(pm−1pm))
odakle se pregrupisavanjem dobija
φ(n)=(pk11…pkmm)(p1−1)⋅…⋅(pm−1)p1⋅…⋅pm=n⋅(p1−1)⋅…⋅(pm−1)p1⋅…⋅pm
Ovo nam daje način za efikasno izračunavanje vrednosti φ(n). Primenjujemo algoritam rastavljanja broja na proste činioce. Svaki put kada naiđemo na prost činilac pi proizvod (koji inicijalizujemo na 1) množimo vrednošću pi−1pi. Nakon toga iz broja uklanjamo sva pojavljivanja činioca pi (za svako pojavljivanje činioca, bez obzira na njegovu višestrukost, proizvod se množi samo jednim činiocem).
Na kraju kao rezultat vraćamo akumulirani proizvod pomnožen vrednošću broja n. Pošto se n menja tokom određivanja njegovih prostih činilaca, bolje rešenje je proizvod na početku inicijalizovati na n.
Složenost odgovara rastavljanju na proste činioce i za broj n iznosi O(√n).
#include <iostream>
using namespace std;
int phi(int n)
{
int p = 2;
int prod = n;
while (p * p <= n) {
if (n % p == 0) {
= (prod / p) * (p - 1);
prod while (n % p == 0) {
/= p;
n }
}
++;
p}
if (n > 1) {
= (prod / n) * (n - 1);
prod }
return prod;
}
int main()
{
int n;
>> n;
cin
<< phi(n) << endl;
cout
return 0;
}