Az alábbi kis progi a Phi(N) értéket adja vissza ami nem jelent mást. Mint azt hogy a relatív prímek száma N-hez 1-től. A relatív prímek olyan számok melyek legnagyobb közös osztója az 1. Itt is lehet agyalni azon hogy akkor most prímtényzős felbontás, miegyebek. Ami jó megoldáshoz vezet de rengeteg munkát igényel mint le programozni mint végrehajtani a számítógépnek. Talán az egyik legelegánsabb megoldás az lnko meghatározására az EUKLIDESZI ALGORITMUS.
Forrás a tovább után---->
#include <iostream>
#include <fstream>
#include <cstdlib>
using namespace std;
int
euklidesz (int i, int j)
{
int maradek = -1;
int elotti = 0;
while (maradek != 0)
{
if ((i % j) == 0)
elotti = i / (i / j);
maradek = (i % j);
i = j;
j = maradek;
}
return elotti;
}
int
main (int argc, char *argv[])
{
int a, b, i, j;
j = 0;
a = atoi (argv[1]);
cout << "Tehát n=" << a << endl << endl;
for (i = 1; i < a; i++)
{
b = euklidesz (i, a);
if (b == 1)
{ //cout<<"("<<i<<","<<a<<")="<<b<<endl;
//cout<<i<<" ";
j++;
}
}
//cout<<endl<<endl;
cout << "Így Phi(n)=" << j << endl;
cout << endl << "Mivel megyünk 1-től.... " << a <<
"-ig és bvizsgáljuk hogy az aktuális " << endl <<
"ciklusváltózó értéke relatív prím-e a megadott értékhez, Euklideszi algoritmussal."
<< endl;
return 0;
}
Futtatva n=20 esetén az alábbi kimenetet kapjuk
Tehát n=20
Így Phi(n)=8
Megjegyzésként fűzön hozzá hogy a progi az első argumentumként kapja meg az n értékét. :)
